POJ 2407 (欧拉函数)

题目链接: http://poj.org/problem?id=2407

题目大意：求小于n且与n互质的正整数个数。

解题思路：

欧拉函数=小于n且与n互质的正整数个数。

公式=n*(1-1/P1)*(1-1/P2)....*(1-1/Pn)，其中Pn为不同的质因数。

欧拉函数的求法有好多。

最简单的是手艹质因数分解，然后套公式计算。

注意特判1的时候ans=0.

#include "cstdio"
#include "map"
using namespace std;
#define LL long long
map<LL,LL> prime_factor(LL n)
{
    map<LL,LL> res;
    for(int i=2;i*i<=n;i++)
        while(n%i==0) {++res[i];n/=i;}
    if(n!=1) res[n]=1;
    return res;
}
int main()
{
    LL n;
    while(scanf("%I64d",&n)!=EOF&&n)
    {
        if(n==1) {printf("0
");continue;}
        map<LL,LL> fac=prime_factor(n);
        LL ret=n;
        for(map<LL,LL>::iterator i=fac.begin();i!=fac.end();i++)
           ret=ret/i->first*(i->first-1);
        printf("%I64d
",ret);
    }
}

13625955

neopenx

2407

Accepted

148K

0MS

C++

573B

2014-11-13 16:20:05