题解 luoguP2303 【[SDOi2012]Longge的问题】

好水的蓝题啊，少数没有看题解做的题

题面简洁明了：求 ${\sum }_{i=1}^{n}gcd(i,n)$i=1∑n​gcd(i,n)

设 $gcd(i,n)=d$gcd(i,n)=d，则 $gcd(i/d,n/d)=1$gcd(i/d,n/d)=1

$d$d显然就是 $n$n的因数

我们对于每个 $d$d，要求有多少 $i$i使得 $gcd(i/d,n/d)=1$gcd(i/d,n/d)=1，设求出有 $x$x个 $i$i，那么对答案的贡献就是 $d\times x$d×x。为什么是这些贡献？很显然，这些 $i$i与 $n$n的 $gcd$gcd就是 $d$d，共 $x$x个这样的 $i$i，所以是 $d\times x$d×x。

因为满足$gcd(i/d,n/d)= $1的$1的i/d $的个数就是与$的个数就是与n/d $互质的数，每个$互质的数，每个i/d $又对应一个$又对应一个i $，个数就是$，个数就是φ(n/d) $。前面说了$。前面说了d $是$是n$的因数，我们枚举所有因数，累加答案即可。

对于每个 $\phi \left(n/d\right)$φ(n/d)， $\sqrt{n}$n ​求即可。

代码：

#include<bits/stdc++.h>
#define ts cout<<"ok"<<endl
#define oo (1e18)
#define int long long
#define LL unsigned long long
#define hh puts("")
using namespace std;
int ans,n;
inline int read(){
    int ret=0,ff=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)){ret=(ret<<3)+(ret<<1)+(ch^48);ch=getchar();}
    return ret*ff;
}
inline int getphi(int x){
    int res=x;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            res=res/i*(i-1);
            while(x%i==0) x/=i; 
        }
    }
    if(x>1) res=res/x*(x-1);
    return res;
}
signed main(){
    n=read();
    int sq=sqrt(n);
    for(int i=1;i<=sq;i++){
        if(n%i==0){
            ans+=getphi(n/i)*i;
            if(i*i!=n) ans+=getphi(i)*(n/i);
        }
    }
    printf("%lld",ans);
    return 0;
}