传送门
先前的大神已经写得很好了。转载下。
在数论中的积性函数：对于正整数n的一个函数 f(n)，当中f(1)=1且当a,b互质，f(ab)=f(a)f(b)，在数论上就称它为积性函数。若某函数f(n)符合f(1)=1，且就算a,b不互质，f(ab)=f(a)f(b)，则称它为完全积性函数。
欧拉函数，gcd(n,k)(当k固定时)都是积性函数
且当i,j互素时，gcd(i*j,m)=gcd（i,m)*gcd(j,m),所以gcd(n,k)是积性函数
同时，积性函数的和也是积性函数
主要考察一个叫积性函数的东西：f(x*y)=f(x)*f(y)，中学数学经常见到。 积性函数还有个性质就是积性函数的和也是积性函数。 可以得到一个式子f(n)=f(p1^a1)*f(p2^a2)*f(p3^a3)*...*f(pk^ak)。不过目前我们不知道这个式子有什么用，6666666666666666。 再看本题，如果n和m互质，那么gcd(i,n*m)=gcd(i,n)*gcd(i,m)。∴gcd(i,n)是积性函数==>Σgcd(i,n)是积性函数。 设f(n)=Σgcd(i,n)，问题转换为求出所有f(pi^ai)。 下面来求f(pi^ai)： 首先明确，如果p是n的约数，那么满足gcd(i,n)==p的i的个数是Φ(n/p)。 证明：gcd(i,n)==p。设i=k*p,n=m*p。 则gcd(k,m)=1，也就是k和m互质，要求出满足条件的i的个数，就是求出i所对应的k的个数，即求m的欧拉函数，m=n/p，所以满足条件的i的个数就是Φ(m)=Φ(n/p)。 好了，用这种原则来求f(pi^ai)，就是枚举pi^ai的每个约数(其实就是pi^t,t<=ai)，然后求使gcd(i,pi^ai)==pi^t满足的i的个数，所以 个数*pi^t就是要求的答案的一部分。 公式： f(pi^ai)=Φ(pi^ai)+pi*Φ(pi^(ai-1))+pi^2*Φ(pi^(ai-2))+...+pi^(ai-1)* Φ(pi)+pi^ai*Φ(1)； 这里可以把求欧拉函数的部分化简，因为f(pi^ai)中只有一个约数pi，所以： Φ(pi^ai)=pi^ai-pi^(ai-1)。 证明：小于pi^ai的正整数个数为p^ai - 1个； 其中，和pi^ai不互质的正整数有(pi*1,pi*2,...,pi*(pi^(ai-1)-1) )共计 pi^(ai-1)-1个。 ∴ Φ(pi^ai)=pi^ai -1 -(pi^(ai-1)-1)=pi^ai-pi^(ai-1)。 然后整理得：f(pi^ai)= pi^ai*(1+ai*(1-1/pi))。 所以， f(n)=n*(1+a1*(1-1/p1))*(1+a2*(1-1/p2))*.…… =n* π(ai*pi+pi-ai)/pi； 本题解决！！！ #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <map> #include <algorithm> using namespace std; #define pi acos(-1) #define endl '\n' #define srand() srand(time(0)); #define me(x,y) memset(x,y,sizeof(x)); #define foreach(it,a) for(__typeof((a).begin()) it=(a).begin();it!=(a).end();it++) #define close() ios::sync_with_stdio(0); cin.tie(0); #define FOR(x,n,i) for(int i=x;i<=n;i++) #define FOr(x,n,i) for(int i=x;i<n;i++) #define W while #define sgn(x) ((x) < 0 ? -1 : (x) > 0) #define bug printf("***********\n"); typedef long long LL; const int INF=0x3f3f3f3f; const LL LINF=0x3f3f3f3f3f3f3f3fLL; const int dx[]= {-1,0,1,0,1,-1,-1,1}; const int dy[]= {0,1,0,-1,-1,1,-1,1}; const int maxn=1005; const int maxx=1e6+100; const double EPS=1e-7; const int mod=998244353; template<class T>inline T min(T a,T b,T c) { return min(min(a,b),c); } template<class T>inline T max(T a,T b,T c) { return max(max(a,b),c); } template<class T>inline T min(T a,T b,T c,T d) { return min(min(a,b),min(c,d)); } template<class T>inline T max(T a,T b,T c,T d) { return max(max(a,b),max(c,d)); } inline LL Scan() { LL Res=0,ch,Flag=0; if((ch=getchar())=='-')Flag=1; else if(ch>='0' && ch<='9')Res=ch-'0'; while((ch=getchar())>='0'&&ch<='9')Res=Res*10+ch-'0'; return Flag ? -Res : Res; } LL val,pri[maxx],vis[maxx]; void init() { for(int i=2;i<maxx;i++) { if(!vis[i])pri[val++]=i; for(int j=0;j<val&&i*pri[j]<maxx;j++) { vis[i*pri[j]]=1; if(i%pri[j]==0)break; } } } LL n; int main() { init(); while(~scanf("%lld",&n)) { LL x=n; LL ans=n; for(int i=0;i<val&&pri[i]*pri[i]<=n;i++) { if(n%pri[i]==0) { LL cnt=0; while(n%pri[i]==0) { n/=pri[i]; cnt++; } ans=(ans/pri[i])*(cnt*pri[i]+pri[i]-cnt); } } if(n>1) { ans/=n; ans*=n+n-1; } cout<<ans<<endl; } }