点击打开链接
//求SUM（gcd(i,n), 1<=i<=n）
/*g(n)=gcd(i,n),根据积性定义g(mn)=g(m)*g(n)(gcd(m,n)==1)所以gcd(i,n)是积性的，所以f(n)=sum(gcd(i,n))是积性的，f(n)=f(p1^a1*p2^a2*...*pn^an)=f(p1^a1)*f(p2^a2)*..*f(pn^an)求f(p1^a1)就可以了,设d为p1^a1的一个因子,gcd(i,n)的个数为phi(n/d)(gcd(i,n/d)==1，符合欧拉函数)p1^a1有a1+1个因子1,p1,p1^2,...,p1^a1f(p1^a1)=phi(p1^a1)+p1*phi(p1^(a1-1))+..+p1^(a1-1)*phi(p1)+p1^a1*phi(1)=p1^a1*(1+a1*(1-1/p1))f(n)=n*(1+a1*(1-1/p1))*(1+a2*(1-1/p2))*..*(1+an*(1-1/pn));*/
#include"stdio.h"
#include"string.h"
#include"math.h"
typedef __int64 LL;
int main()
{int i;int n,a;LL ans;int b;while(scanf("%d",&n)!=-1){ans=n;b=sqrt(1.0*n);for(i=2;i<=b;i++){if(n%i==0){a=0;while(n%i==0){n/=i;a++;}ans=ans+ans*a*(i-1)/i;}}if(n!=1)ans=ans+ans*(n-1)/n;printf("%I64d
",ans);}return 0;
}