P2303 [SDOI2012] Longge 的问题

首先%%%zzz

人生中没做过几道数论题，经过 zzz 的悉心指导大概算是会了这道…题

题目要求为求

$$∑ ^n_{i=1}gcd(i,n)$$

一道非常套路的题，感觉做这题可以总结出两个思想：

• 向熟悉的函数进行化归
• 拆解 gcd 的因数，考虑因数的贡献

这样就可以考虑对原式的每个因数考虑贡献，原式可以化为

$$∑_{d|n}d×∑_{i=1}^{n}[gcd(i,n)=d]$$

因为 $gcd(n,m)=d$ 可以推出 $gcd(n/d,m/d)=1$，所以可以向欧拉函数化归：

$$∑_{d|n}d×∑_{i=1}^{\frac{n}{d}}[gcd(i,\frac{n}{d})=1]$$

发现后式就是欧拉函数定义式，因此直接推出：

$$∑_{d|n}d×φ(\frac{n}{d})$$

刚学数论，另外需要注意：枚举因数从 $i$ 到 $i*i<=n$ 的时候，一下可以筛去两个因数，但是要考虑完全平方数是两个相同的因数的情况。

code:

#include<bits/stdc++.h>
using namespace std;
long long eular(long long n){
    long long ans=n;
    for(long long i=2;i*i<=n;++i){
        if(n%i==0){
            ans=ans/i*(i-1);
            while(n%i==0)n/=i;
        }
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}
int main(){
    long long n,ans=0;
    cin>>n;
    for(register long long i=1;i*i<=n;++i)
        if(n%i==0)
            if(i*i==n)ans+=i*eular(n/i);
            else ans+=i*eular(n/i)+(n/i)*eular(i);
    cout<<ans;
    return 0;
}