题目链接: 

题目大意：求小于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 longmap
     
       prime_factor(LL n){    map
      
        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\n");continue;}        map
       
         fac=prime_factor(n);        LL ret=n;        for(map
        
         ::iterator i=fac.begin();i!=fac.end();i++)           ret=ret/i->first*(i->first-1);        printf("%I64d\n",ret);    }}
        
       
      
     

 

13625955

Accepted

148K

0MS

573B

2014-11-13 16:20:05