1. 题目

biubiu

2. 题解

这题不能直接预处理出 phi，因为数组开不下。。

设 gcd(i,n)==k ->gcd(i/k,n/k)==1 。

所以 i/k 有 phi[n/k] 种选法 。

ans=sigma(phi[k])1<=k<=n;

还是过不了。。。

设 f[d] 为 gcd(i,n)==d 的方案数，d 是 n 的约数

ans=sigma(d×f[d]) !

枚举约数 d，可以在 sqrt(d) 内求 phi(d)

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>void read(T &in){
    char c=getchar();int f=1;in=0;
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){in=in*10+c-'0';c=getchar();}
    in*=f;
}
ll n,m,ans;
ll phi(ll x){
    ll t=x;
    for(int i=2;i<=m;++i){
        if(x%i==0){
            t=t/i*(i-1);
            while(x%i==0)x/=i;
        }
    } 
    if(x>1)t=t/x*(x-1);
    return t;
}
int main(){
    freopen("a.in","r",stdin);
    read(n);m=sqrt(n);
    for(int i=1;i<=m;++i){
        if(n%i==0){
            ans+=(ll)i*phi(n/i);
            if(i*i<n)ans+=(ll)(n/i)*phi(i);
        }
    }
    printf("%lld",ans);
    return 0;
}