POJ2480 Longge's problem【趁性函数】

POJ2480 Longge's problem【乘性函数】

题目链接：

http://poj.org/problem?id=2480

题目大意：

给一个正整数n，求Σgcd(i，n)，(1 <= i <= n)。

思路：

如果m，n互质，则gcd(i，m*n) = gcd(i，m) * gcd(i，n)，所以gcd是乘性函数。

因为乘性函数的和函数也是乘性函数，所以Σgcd(i，N)也是乘性函数。

首先考虑gcd(x，n) = 1，这样的数和刚好为欧拉函数之和sum( φ(n))，现在考虑gcd(x，n) = p

的情况，因为gcd(x/p,n/p) = 1，就变成了欧拉函数之和sum(φ(n/p))，所以gcd(x，n) = p，这种

情况下结果为sum( p*phi(n/p) )，p为n的约数。总结就是Σgcd(i，N) = Σp*phi(n/p)，p是n的约数。

设Σp*phi(n/p) = H(n)，因为H(n)为乘性函数，H(n) = H(p1^k1) * H(p2^k2) * … * H(pn^kn)，

对于素数p^k，有：φ(p^k) = p^k - p^(k-1)，

所以H(pi^ki) = p^k - p^(k-1) + p*(p^(k-1) - p^(k-2)) + p^2*(p^(k-2) - p^(k-3)) + ……

                     = p^k + k*(p^k - p^(k-1) )

那么解题步骤为将N分解素因子，对每个素因子计算H(pi^ki)，最后加起来。

参考博文：http://www.cnblogs.com/JS-Shining/archive/2012/05/14/2500661.html

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

int main()
{
    __int64 n,i,N,a,p,ans;
    while(~scanf("%I64d",&n))
    {
        N = n;
        ans = n;
        for(i = 2; i*i <= N; ++i)
        {
            if(n % i == 0)
            {
                a = 0;
                p = i;
                while(n % p == 0)
                {
                    a++;
                    n /= p;
                }
                ans += ans*a*(p-1)/p;
            }
        }
        if(n != 1)
            ans += ans*(n-1)/n;

        printf("%I64d\n",ans);
    }

    return 0;
}