poj 2480 （歐拉函數應用）

//求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^a1
	f(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\n",ans);
	}
	return 0;
}