luogu P3911

题目

修复了一些小bug,(。・_・。)ノI’m sorry~

给出集合 \(A\),设 \(n=\mid A\mid\),求 \(\sum_{i=1}^n\sum_{j=1}^n\text{lcm}(A_i,A_j)\)。

摸到这道题,我们马上就可以发现 \(A\) 中的元素是无序的,题目中给出的式子没法化简,所以我们不得不考虑转化式子。

数据范围 \(1\le A_i\le5e4\),这就很好办了……

开一个桶(这里用数组 \(t\) 表示),\(t[i]\) 表示数 \(i\) 在集合中出现的次数。

这样原式就转化为了:

\[\sum_{i=1}^n\sum_{j=1}^n\text{lcm}(i,j)\times t[i]\times t[j] \]

注意此后 \(n\) 指集合 \(A\) 中元素的最大值。

这样好像就可以转化 \(\text{gcd}\) 求解了。

(为了此篇题解更通俗易懂,接下来的推导会有些冗余部分,见谅~)

愉快的推式子时间~:

\[\large \begin{aligned} &\sum_{i=1}^n\sum_{j=1}^n\text{lcm}(i,j)\times t[i]\times t[j]\\ &\Rightarrow\sum_{i=1}^n\sum_{j=1}^n\frac{i\times j}{\text{gcd}(i,j)}\times t[i]\times t[j]\\ &\Rightarrow\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^n\frac{i\times j}{[\text{gcd}(i, j)=d]\times d}\times t[i]\times t[j]\\ &\Rightarrow\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\frac{i d\times jd}{[\text{gcd}(i, j)=1]\times d}\times t[id]\times t[jd]\\ &\Rightarrow\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}d\times i\times j\times[\text{gcd}(i, j)=1]\times t[id]\times t[jd]\\ &\Rightarrow\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}d\times i\times j\times\sum_{k\mid i,k\mid j}\mu(k)\times t[id]\times t[jd]\\ &\Rightarrow\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{k\mid i,k\mid j}\mu(k)\times d\times i\times j\times t[id]\times t[jd]\\ &\Rightarrow\sum_{d=1}^n\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{kd}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{kd}\rfloor}\mu(k)\times d\times ik\times jk\times t[ikd]\times t[jkd]\\ &\Rightarrow\sum_{s=1}^ns\times\sum_{k\mid s}\mu(k)\times k\ (\sum_{i=1}^{\lfloor\frac{n}{s}\rfloor}i\times t[is])^2 \end{aligned} \]

一些解释(大佬可直接跳过):

  1. \(s=kd\)。
  2. 结果中的平方为上面的式子中的 \(i\) 和 \(j\),他俩其实是一样的。

最后,我们使用线性筛预处理 \(\sum_{k\mid s}\mu(k)\times k\),输入时直接处理 \(t\),然后暴力就完了。

代码按照上面的暴力即可,就不给了 QVQ。

上一篇:ARC123E Training


下一篇:C# OpenFileDialog上传附件