4939 欧拉函数

 

 时间限制: 1 s

 空间限制: 1000 KB

 题目等级 : 钻石 Diamond

 

 

 

题目描述 

Description

输入一个数n，输出小于n且与n互素的整数个数

输入描述 

Input Description

包含多组数据，n=0时结束

测试数据组数不会很多，不必先打表后输出

输出描述 

Output Description

一组数据一行

样例输入 

Sample Input

364684

346

5432

11

24

0

2333333

233333333

0

233333333333333

2333333333333333333333333333333333333333333333333

 

样例输出 

Sample Output

165120

172

2304

10

8

数据范围及提示 

Data Size & Hint

1<n<9223372036854775807

注意细节的优化，否则第九组数据可能超时

分类标签 Tags 

 

暂无标签

一步步按照老师讲的，转化成代码，结果数据卡内存。

40分代码（MLE）

#include
     
      #include
      
       using namespace std;#define N 100001int n,a[N]={
   0};int main(){    while(scanf("%d",&n)==1){        if(!n) break;        double s=n;        int i,j;        for(i=2;;i++){            if(n==1) break;            for(j=0;;j++){                if(n%i) break;                n/=i;            }            a[i]=j;        }        int e=i;        for(i=2;i<=e;i++){            if(!a[i]) continue;            double t=i;            s*=(1.0-1.0/t);        }        printf("%d\n",(int)s);        for(int i=1;i<=e;i++) a[i]=0;    }    return 0;}
      
     

看题解，优化的代码

AC代码1：

#include
     
      #include
      
       using namespace std;int main(){    long long n,ans;    while(cin>>n){        if(!n) break;        ans=n;        if(n%2==0){            while(n%2==0) n/=2;            ans/=2;        }        for(long long i=3;i*i<=n;i+=2){            if(n%i==0){                while(n%i==0) n/=i;                ans=ans/i*(i-1);            }        }        if(n>1) ans=ans/n*(n-1);        cout<
       
        <
       
      
     

 AC代码2：

#include
     
      int euler_phi(int p){    int phi=p;    for(int i=2;i*i<=p;i++){        if(!(p%i)){            phi=phi-phi/i;            while(!(p%i))                p/=i;        }    }    if(p>1)        phi=phi-phi/p;    return phi;}int main(){    int p;    while(scanf("%d",&p),p)        printf("%d\n",euler_phi(p));    return 0;}