题目传送门：链接。
能自己推出正确的式子的感觉真的很好！
题意简述：
求(sum_{i=1}^{n}gcd(i,n))。(nleq 2^{32})。
题解：
我们开始化简式子：
(sum_{i=1}^{n}gcd(i,n))
(=sum_{j=1}^{n}left(j imessum_{i=1}^{n}left[gcd(i,n)=j ight] ight))
(=sum_{j=1}^{n}left(j imessum_{i=1}^{n}left[gcd(i/j,n/j)=1 ight]left(j|i,j|n ight) ight))
(=sum_{j=1}^{n}left(j imesvarphileft(n/j ight)left(j|n ight) ight))
(=sum_{j|n}left(j imesvarphileft(n/j ight) ight))
到这里就可以直接计算了。
但是还可以进一步化简！（以下的(p)为质数）
(sum_{j|n}(j imesvarphi(n/j)))
(=sum_{j|n}(n/j imesvarphileft(j ight)))
(=sum_{j|n}(n/j imes(jcdotprod_{p|j}frac{p-1}{p})))
(=sum_{j|n}(ncdotprod_{p|j}frac{p-1}{p}))
(=n imessum_{j|n}prod_{p|j}frac{p-1}{p})
接下来我们令(n=p_1^{b_1}p_2^{b_2}p_3^{b_3}cdots p_k^{b_k})，并定义(f_i=frac{p_i-1}{p_i})。
那么(n)的因子(j)可以表示为：(j=p_1^{c_1}p_2^{c_2}p_3^{c_3}cdots p_k^{c_k})，满足(0leq c_ileq b_i)。
那么(prod_{p|j}frac{p-1}{p}=prod_{i=1}^kf_i[c_i>0])。
我们观察一类(prod_{i=1}^kf_i[c_i>0])相等的(j)，它们必要满足在(i)相等的情况下，(c_i)同时大于0或(c_i)同时等于0。
那么这一类的(j)有多少个呢？如果这类(j)有质因子(p_{q_1},p_{q_2},p_{q_3},cdots,p_{q_g})。
那么这类(j)的答案为(prod_{i=1}^gf_{q_i})，而个数为(prod_{i=1}^gb_{q_i})。
(b_i)就是原来(n)的质因数分解的指数。
那么对答案的贡献为：(prod_{i=1}^gchi_{q_i})。这里(chi_i=f_icdot b_i)。
发现每一个质因子的贡献都是独立的，那么最后我们枚举(n)的每一个质因子取不取，得到最后的答案：(ncdotprod_{i=1}^{k}(chi_i+1))。
举个例子：如果(n)只有(3)个质因子，那么答案为(ncdot(1+chi_1+chi_2+chi_3+chi_1chi_2+chi_1chi_3+chi_2chi_3+chi_1chi_2chi_3))。
显然可以化简为：(ncdot(chi_1+1)cdot(chi_2+1)cdot(chi_3+1))。
当然可以类比到质因数更多的情况。
总之，答案就是：(ncdotprod_{i=1}^{k}frac{b_icdot p_i-b_i+p_i}{p_i})。
代码：
1 #include<cstdio> 2 long long n; 3 long long f(){ 4 long long ans=n; long long i; 5 for(i=2;i*i<=n;++i) if(n%i==0){ 6 int b=0; 7 while(n%i==0) ++b,n/=i; 8 ans/=i; 9 ans*=b*i-b+i; 10 } if(n>1) ans/=n, ans*=n+n-1; 11 return ans; 12 } 13 int main(){ 14 scanf("%lld",&n); 15 printf("%lld",f()); 16 return 0; 17 }