首页 > 代码库 > poj 2480 欧拉函数+积性函数+GCD

poj 2480 欧拉函数+积性函数+GCD

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


首先要会欧拉函数:先贴欧拉函数的模板,来源于吉林大学的模板:

//欧拉函数PHI(n)表示的是比n小,并且与n互质的正整数的个数(包括1)。
unsigned euler(unsignedx)
{// 就是公式
    unsigned i, res=x;
    for(i = 2; i < (int)sqrt(x * 1.0) + 1; i++)
        if(x%i==0) {
            res = res / i * (i - 1);
            while(x % i == 0) x /= i; // 保证i一定是素数
    }
    if(x > 1) res = res / x * (x - 1);
    return res;
}

然后欧拉函数在本题中用到的一些性质:
1.n为素数时,PHI(n) = n - 1。因为每个比n小的正整数都和n互素。当n为素数pk次方时,PHI(n) = p ^ k - p ^ (k - 1)。因为在1n之间的正整数只有p的倍数和n不互素,这样的数有(p ^ k / p)个。
2.
如果mn互素,即GCD(m, n) = 1,那么PHI(m * n) = PHI(m) * PHI(n)

然后说本题:
我参考了这个题解,代码也看了o(╯□╰)o,不过人家写的很好啊,膜拜~~

http://blog.csdn.net/terry__j/article/details/7403923

然后贴我的代码:

/****************************************欧拉函数+积性函数
    by Pilgrim 2014.5.10
注意:1、//ans=ans*(1+ai*(i-1)/i);--WA,二逼了
         ai/i很可能不是整除,所以这么写
          ans=ans+ans*ai*(i-1)/i;
\****************************************/

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cmath>

using namespace std;

#define lint long long

int main()
{
    lint n,sqr,tmp,ai,ans,ret;

    while(scanf("%lld",&n)!=EOF)
    {
        tmp=n;
        ans=n;
        sqr = (lint)sqrt(n*1.0)+1;
        for(lint i=2;i<sqr;i++)
        {
            if(tmp%i == 0)
            {
                tmp/=i,ai=1;
                while(tmp%i == 0)tmp/=i,ai++;

                //ans=ans*(1+ai*(i-1)/i);
                ans=ans+ans*ai*(i-1)/i;
            }
        }
        if(tmp!=1)//ans=ans*(1+(tmp-1)/tmp);
            ans=ans+ans*(tmp-1)/tmp;
        printf("%lld\n",ans);
    }

    return 0;
}