POJ2480:Longge's problem（欧拉函数的应用）

题目链接：传送门

题目需求：

Given an integer N(1 < N < 2^31),you are to calculate ∑gcd(i, N) 1<=i <=N. 这题就是上一篇博客的变形。

题目解析：首先先求出与N互质的个数，即N的欧拉函数值，之后分解出N的因子来，求解方法如下。

证明：

要求有多少个 i 满足gcd(i, N) = d 如果gcd(i, N) = d，则gcd(i/d, N/d) = 1 由于i <= N，所以 i/d <= N/d，转化为求多少个不大于N/d的数与N/d互质，而这就是欧拉函数所以有phi(N/d)个 i 满足gcd(i, N) = d，所以∑d*phi(N/d)即为答案。

我搜了大部分人的题解都是利用乘性函数做的，思想我附在代码下面，因为已A，我就不用他们那种方法了。

代码：（欧拉函数打表204ms)

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

typedef long long ll;

using namespace std;

ll phi[];

ll f[];

ll sum,n,t,tt,i;

void init()

{

    memset(phi,,sizeof(phi));

    phi[]=;

    for(int i=; i<=; i++)

    {

        if(!phi[i])

        {

            for(int j=i; j<=; j=j+i)

            {

                if(!phi[j]) phi[j]=j;

                phi[j]-=phi[j]/i;

            }

        }

    }

}

int main()

{

    init();

    while(scanf("%I64d",&n)!=EOF)

    {

        tt=;

        for(i=; i*i<n; i++)

        {

            if(n%i==)

            {

                f[tt++]=i;

                f[tt++]=n/i;

            }

        }

        if(i*i==n)

            f[tt++]=i;

        sort(f,f+tt);

        if(tt==)

        {

            tt=*n-;

            printf("%I64d\n",tt);

            continue;

        }

        t=n;

        sum=n;

        for(i=; i*i<=t; i++)

        {

            if(t%i==)

            {

                sum-=sum/i;

                t/=i;

                while(t%i==)

                    t/=i;

            }

        }

        if(t!=)

            sum-=sum/t;

        sum+=n;

        for(i=; i<tt; i++)

        {

            if(n/f[i]>=)

            {

                ll temp=n/f[i];

                ll cot=temp;

                for(ll z=; z*z<=temp; z++)

                {

                    if(temp%z==)

                    {

                        t/=z;

                        cot-=cot/z;

                        while(temp%z==)

                            temp/=z;

                    }

                }

                if(temp!=) cot-=cot/temp;

                sum+=cot*f[i];

                continue;

            }

            sum+=(phi[n/f[i]])*f[i];

        }

        printf("%I64d\n",sum);

    }

    return ;

}

下面推导没看懂。。。。。

积性函数：若任取互质的两个数m,n，都有f(m*n) = f(m)*f(n)，那么f就是积性函数

容易证明gcd(i,n)是积性函数，即：如果n = m1*m2 且gcd(i,m1*m2) = gcd(i,m1)*gcd(i,m2). 然后根据具体数学上的结论：积性函数的和也是积性的，所以如果我们设所求答案是f(n) 则： f(n) = f(m1)*(m2) 其中，m1*m2 = n 且m1,m2互质！

经过因子分解，那种只要求到f(p^k)就可以利用积性把所有结果相乘得到最后答案。

还要一个结论： f(n) = sum(p * phi(n/p)) 其中p是n的因子，phi(n/p) 是从1到n有多少个数和n的gcd是p, 这个结论比较好证明的。

所以求f(p^k)转化成求phi(p^i) i =0....k; 而根据公式phi(p^i) = (p-1)*p^(i-1)可以求出，这样整个问题就解决了。

巴特西

POJ2480:Longge's problem（欧拉函数的应用）

最新文章

热门文章