学步园

题目链接：http://poj.org/problem?id=2480

这个题我很早就提交过了，但是之前不知到是哪儿膜拜来的代码。。

今天别人问我，我又回去看了看，发现这个题目已经不是那么难了

按照自己的思路写了写，先开始一直莫名的TLE，后来把n为素数的情况特判了一下

于是就360MS卡过去了。。。

我的代码：

#include<stdio.h>
typedef long long LL;

LL num[70000];

LL eular(LL n)
{
	LL i,ret=1;
	for(i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			n=n/i;
			ret=ret*(i-1);
			while(n%i==0)
			{
				n=n/i;
				ret=ret*i;
			}
		}
	}
	if(n>1)
		ret=ret*(n-1);
	return ret;
}

int main()
{
	LL i,n,k,ans;
	while(scanf("%lld",&n)!=EOF)
	{
		k=0,ans=0;
		for(i=1;i*i<n;i++)
		{
			if(n%i==0)
			{
				num[k++]=i;
				num[k++]=n/i;
			}
		}
		if(i*i==n)
			num[k++]=i;
		if(k==2)
		{
			printf("%lld\n",2*n-1);
			continue;
		}
		for(i=0;i<k;i++)
			ans=ans+num[i]*eular(n/num[i]);
		printf("%lld\n",ans);
	}
	return 0;
}