U204742
joke3579
·
·
个人记录
首先推一下春卷饭和《ふたりの》。
本题的标程是杜教筛优化求值，来自 @APJifengc，在 @CDsidi 的O(n)解法上改善得到。@LYinMX 同样提供了一种常数未测试的 O(n) 解法，下方给出。该题同样有 O(n\operatorname{log}n) 的解法，但显然不够优秀。
本题解的目的在于叙述该题解题思路，将按算法优秀程度自劣至优分别给出。
方法1：暴力
时间复杂度 O(n^2\log n)，不再赘述。
方法2：推公式
\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)
观察公式。显然，对于gcd(m,n)与gcd(n,m)，二者的值是相同的。因此，我们可以这样拆分公式：
\begin{aligned} \sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j) &= 2\sum_{i=1}^{n}\sum_{j=1}^{i}gcd(i,j) + \sum_{i=1}^ni \\ &= 2\sum_{i=1}^{n}\sum_{j=1}^{i}gcd(i,j)\ + \frac{n(n+1)}{2} \end{aligned}
只需讨论前半部分即可。
该部分的化简与longge的问题相同，这里不再赘述：
\end{aligned}
使用筛法求得每个数的因子，进而算得j\times \varphi(i/j)，并 在O(n) 时间复杂度下求得结果。
理论时间复杂度： O(n\sqrt{n} \ \times 因子个数)。
方法3：性质法
本法由 @LYinMX 提供。
我们设
f(n) = \sum_{i|n}i\times \varphi(\frac ni)
可以求得
\begin{aligned}
& 1,\ n=1 \\
& f(\frac{n}{p^c})\times {p^c}\times(1+\frac{c(p-1)}{p}),\ n>1
\end{aligned}
\right.
其中，p为n最小的质因子，且p\perp \frac n{p^c} 。
因此，可以在O(n)时间复杂度下算得f(n)的值，并在O(n)时间复杂度下求得结果。
方法4：继续推
本法由 @CDsidi 提供。
\sum_{i=1}^{n}\sum_{j|i}j\times \varphi(\frac ij)
观察公式。有：
\sum_{i=1}^{n}\sum_{j|i}j\times \varphi(\frac ij)
&= \sum_{i=1}^{n}\sum_{j|i}\frac ij\times \varphi(j)\\
&= \sum_{i=1}^{n}i\times\sum_{j|i}\frac {\varphi(j)}j
\end{aligned}
我们现在讨论\sum_{j|i}\frac {\varphi(j)}j的全局贡献。具体地，我们考虑j取[1,n]中的整数，并讨论j的每个取值对结果的贡献度。因此，我们有
\sum_{j=1}^{n}\frac {\varphi(j)}j \sum_{i=1}^{n}i\times [\ j\ |\ i\ ]
后半部分即为贡献度计算式。具体地，若j|i，则该处的j对结果的贡献度增加i。
观察贡献度计算式。易得，i对结果有贡献当且仅当i可以被表示为k\times j的形式，这里k \in \mathbb{N^+}。我们可以算得此处k的上下界。易得k的下界为1，上界为\lfloor \frac nj \rfloor。
改写得
\sum_{j=1}^{n}\frac {\varphi(j)}j \sum_{k=1}^{\lfloor \frac nj \rfloor}k\times j
&= \sum_{j=1}^{n} \varphi(j) \sum_{k=1}^{\lfloor \frac nj \rfloor}k \\
&= \sum_{j=1}^{n} \varphi(j) \frac {(1+\lfloor \frac nj \rfloor)\times \lfloor \frac nj \rfloor}{2}
\end{aligned}
带回原式，我们有标程式
\frac{n(n+1)}{2} + \sum_{j=1}^{n} \varphi(j)\times (1+\lfloor \frac nj \rfloor)\times \lfloor \frac nj \rfloor
因此做到了小常数O(n)求解。
优化：杜教筛
观察标程式。使用杜教筛优化即可。