「POJ2480」Longge's problem

题意：给定 $n$，求 $\sum_{i=1}^{n} \gcd(i,n)$，$1<n<2^{31}$。

很明显，暴力求法绝对会 TLE。

我们需要把式子转换一下，设 $\gcd(i,n)=p$，很明显 $p|n$；

我们把两边同时除以 $p$，得到：

$$\gcd(i/p,n/p)=1$$

即求与 $n/p$ 互质的数的个数，即 $\varphi(n/p)$。

所以答案就是：

$$\sum_{d|n}d\varphi(\frac{n}{d})$$

直接求约数和欧拉函数即可。

code:

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
long long n,ans;
long long eular(long long x)
{
    long long ans=x;
    for(long long i=2;i*i<=x;i++)
        if(x%i==0)
        {
            ans=ans/i*(i-1);
            while(x%i==0)
                x/=i;
        }
    if(x>1)
        ans=ans/x*(x-1);
    return ans;
}
int main()
{
    while(scanf("%lld",&n)!=EOF)
    {
        ans=0;
        for(long long i=1;i*i<=n;i++)
            if(n%i==0)
            {
                long long j=n/i;
                ans=ans+i*eular(j);
                if(i!=j)
                    ans=ans+j*eular(i);
            }
        printf("%lld\n",ans);
    }
    return 0;
}