P1390 公约数的和
原题链接
自己推出式子的感觉真好。
来一个 O ( n ) O(n) O(n) 的，不需要任何高深知识，只要会线性欧拉筛法即可的做法。
简单而言就是套路的将求 gcd \gcd gcd 转为枚举 gcd \gcd gcd，求互质的数，然后将求和式子变化变化就行了。
∑ i = 1 n ∑ j = i + 1 n gcd ( i , j ) = ∑ i = 1 n ∑ j = 1 n gcd ( i , j ) 2 ， ∑ i = 1 n ∑ j = 1 n gcd ( i , j ) = ∑ d = 1 n d ∑ i = 1 n ∑ j = 1 n [ gcd ( i , j ) = d ] = ∑ d = 1 n d ∑ i = 1 ⌊ n d ⌋ ∑ j = 1 ⌊ n d ⌋ [ gcd ( i , j ) = 1 ] = ∑ d = 1 n d × 2 ∑ i = 1 ⌊ n d ⌋ ∑ j = 1 i [ gcd ( i , j ) = 1 ] = ∑ d = 1 n d × 2 ∑ i = 1 ⌊ n d ⌋ φ ( i ) \begin{aligned} \sum_{i=1}^{n}\sum_{j=i+1}^{n}\gcd(i,j)&=\frac{\begin{aligned}\sum_{i=1}^{n}\sum_{j=1}^{n}\gcd(i,j)\end{aligned}}{2} ， \\\sum_{i=1}^{n}\sum_{j=1}^{n}\gcd(i,j)&=\sum_{d=1}^{n}d\sum_{i=1}^{n}\sum_{j=1}^{n}[\gcd(i,j)=d] \\&=\sum_{d=1}^{n}d\sum_{i=1}^{ \left \lfloor \frac{n}{d} \right \rfloor }\sum_{j=1}^{\left \lfloor \frac{n}{d} \right \rfloor}[\gcd(i,j)=1] \\&=\sum_{d=1}^{n}d\times 2\sum_{i=1}^{ \left \lfloor \frac{n}{d} \right \rfloor }\sum_{j=1}^{i}[\gcd(i,j)=1] \\&=\sum_{d=1}^{n}d\times 2\sum_{i=1}^{ \left \lfloor \frac{n}{d} \right \rfloor }\varphi(i) \end{aligned} i=1∑nj=i+1∑ngcd(i,j)i=1∑nj=1∑ngcd(i,j)=2i=1∑nj=1∑ngcd(i,j)，=d=1∑ndi=1∑nj=1∑n[gcd(i,j)=d]=d=1∑ndi=1∑⌊dn⌋j=1∑⌊dn⌋[gcd(i,j)=1]=d=1∑nd×2i=1∑⌊dn⌋j=1∑i[gcd(i,j)=1]=d=1∑nd×2i=1∑⌊dn⌋φ(i)
求一下欧拉函数的前缀和，就可以 O ( n ) O(n) O(n) 解决了。