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

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

2024-07-04 00:24:05   228人阅读

题目：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为素数p的k次方时，PHI(n) = p ^ k - p ^ (k - 1)。因为在1到n之间的正整数只有p的倍数和n不互素，这样的数有(p ^ k / p)个。
2. 如果m和n互素，即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;
}



联系
我们