洛谷 P2303 约数&欧拉函数&简单推式子
_Cheems
·
·
个人记录
题意
求 \sum\limits_{i=1}^{n} gcd(i,n)，n\le 2^{31}。
思路
看到 \rm gcd 马上考虑推式子，使得某个项含有 \phi。
观察 gcd(i,n) 的取值，显然是很少的，那么考虑贡献法：
\sum\limits_{i=1}^{n} gcd(i,n)=\sum\limits_{d\mid n} {d*\sum[gcd(i,n)=d]}
如何快速求后面这一项呢？这里引入 \rm gcd 的一个性质：
gcd(ka,kb)=k*gcd(a,b)
所以 \phi 可以这样得到：
gcd(ka,kb)=k \to gcd(a,b)=1
所以：
\sum[gcd(i,n)=d]
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum\limits_{i=1}^{\frac nd}[gcd(i,\frac nd)=1]
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\phi(\frac nd)
综上：
\sum\limits_{i=1}^{n} gcd(i,n)=\sum\limits_{d\mid n}d*\phi(\frac nd)
枚举因数并计算欧拉函数即可，时间复杂度 O(klogn)，k 表示 n 的约数个数。
提交记录。