欧拉函数 BZOJ2705

2705: [SDOI2012]Longge的问题

Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 3154 Solved: 1968
[Submit][Status][Discuss]

Description

Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。

Input

一个整数，为N。

Output

一个整数，为所求的答案。

Sample Input

Sample Output

枚举n的因子，对于一个因子x，求与n只有这一个因子x的数目，显然如果暴力的话就是for(int i=x;i<=n;i+=x)然后判断每个i是否与n只有一个因子，从而求得数目然后乘上x。

可以用欧拉函数简化这一过程，因子为x，那么与他成对那个就是y=n/x。我们只需求出小于y并与y互质的数目就可以了，因为与y互质，那么与k*y(显然ky可以等于n)仍然互质，也就是说找出来的每个z。必定满足gcd(n,z)==1且z*x<n，那么gcd(n,z*x)肯定就只有x这一个因子了，从而简化了过程

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long LL;

LL phi(LL x)

{

    LL ans=x;

    for(LL i=; i*i<=x; ++i)

    {

        if(x%i==) ans=ans*(i-)/i;

        while(x%i==) x/=i;

    }

    if(x>) ans=ans*(x-)/x;

    return  ans;

}

int main()

{

    LL n;

    scanf("%lld",&n);

    LL ans=;

    for(LL i=sqrt(n); i>=; --i)

    {

        if(n%i==)

        {

            ans+=phi(n/i)*i;

            if(i*i!=n) ans+=phi(i)*(n/i);

        }

    }

    printf("%lld\n",ans);

}

巴特西