[数论][积性函数][欧拉函数性质] POJ2480

https://cn.vjudge.net/problem/POJ-2480

题意：给定int范围内的整数N，要求gcd(i,N)之和，其中1<=i<=N

大佬们说积性函数的和也是积性函数那我就先这么说吧

附上积性函数资料 https://blog.csdn.net/skywalkert/article/details/50500009

如果搞出来这个∑gcd(i,N)是一个积性函数就可以进行推导了。。

令f(n)=  ∑gcd(i,N),由于∑gcd是积性函数，所以f(ab)=f(a)*f(b);将N素数分解，得到f(n)=Πf(pi^ai)。到了这一步还是看不出来怎么能快速操作，现在得想办法看看怎么求f(pi^ai)=∑gcd(i,pi^ai);我们注意到gcd(i,pi^ai) 的取值只有可能是pi^k,(k=0,1,2…ai)，所以可以枚举这个结果，当gcd(i,pi^ai)==pi^k时一定有i=m*pi^k&&gcd(m,pi^(ai-k))==1，那么有多少个i就是有多少个m，也就是这样的i有phi(pi^(ai-k))个，那么问题就进一步转化为怎么求pi^(ai-k)了，这个的话就是对欧拉函数的性质的熟悉程度了：若p为素数，则phi(p^k)=p^k-p^(k-1) !

到这里的话把上面的一综合就可以得到最后的结果了。。只需要将N质因数分解然后复杂度就是O(k+sqrt(N))的。（k为质因子个数）；

#include 
#include
#include
#include

using namespace std;

typedef long long LL;

LL p[55],n[55],k;

void div(int A)// get the prime div of A
{
    //int A=n;
    k=0;
    if(A%2==0)
    {
        p[++k]=2;
        n[k]=0;
        while(!(A%2))
        {
            n[k]++;
            A/=2;
        }
    }
    int sa=sqrt(A+0.5);
    for (int i=3;i<=sa;i+=2)
    {
        if(A%i==0)
        {
            p[++k]=i;
            n[k]=0;
            while(!(A%i))
            {
                n[k]++;
                A/=i;
            }
        }
    }
    if(A!=1)
    {
        p[++k]=A;
        n[k]=1;
    }
}

int main()
{
    int num;
    LL ans;
    while(~scanf("%d",&num))
    {

        ans=num;
        div(num);
        for (int i=1;i<=k;i++)
        {
            ans*=(n[i]*p[i]-n[i]+p[i]);
            ans/=p[i];
        }

        printf("%lld\n",ans);
    }
    return 0;
}