记录编号	43528	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 最大公约数和	最终得分	100
用户昵称	Czb。	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2012-10-11 09:44:31	内存使用	3.18 MiB

#include<stdio.h>

typedef long long Int;

Int n,t,ans,prime[20000];

bool flag[1000000];

Int ou(Int k)
{
    Int i,s=k,tmp=k;
    for(i=1;i<=t&&prime[i]*prime[i]<=k;i++)
    {
        if(k%prime[i]==0)s=s/prime[i]*(prime[i]-1);
        while(k%prime[i]==0)k/=prime[i];
    }
    if(k>1)s=s/k*(k-1);
    return s;
}

int main()
{
    freopen("gcdsum.in","r",stdin);
    freopen("gcdsum.out","w",stdout);
    Int i,j;
    scanf("%lld",&n);
    for(i=2;i*i<=n;i++)
    {
        if(!flag[i])
        {
            prime[++t]=i;
            for(j=i+i;j*j<=n;j+=i)
            {
                flag[j]=true;
            }
        }
    }
    for(i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            if(i*i==n)
            {
                ans+=ou(i)*i;
                break;
            }
            ans+=ou(i)*n/i;
            ans+=ou(n/i)*i;
        }
    }
    printf("%lld\n",ans);
    return 0;
}