NYOJ-333

原题链接：http://acm.nyist.net/JudgeOnline/problem.php?pid=333

分析:直接套用欧拉公式即可！

mdd的烦恼

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #define maxn 65545
 6 using namespace std;
 7 int flag[maxn]={0};
 8 int prime[maxn];
 9 int cnt;
10 void selPrime()
11 {
12     cnt=0;
13     for(int i=2;i<maxn;i++)
14     {
15         if(flag[i])continue;
16         prime[cnt++]=i;
17         for(int j=1;j*i<maxn;j++)
18         flag[j*i]=1;
19     }
20 }
21 int Eular(int n)
22 {
23     int res=1;
24     for(int i=0;i<cnt&&prime[i]*prime[i]<=n;i++)
25     {
26         if(n%prime[i]==0)
27         {
28             res*=prime[i]-1;
29             n/=prime[i];
30             while(n%prime[i]==0)
31             {
32                 res*=prime[i];
33                 n/=prime[i];
34             }
35         }
36     }
37     if(n>1)res*=n-1;
38     return res;
39 }
40 int main()
41 {
42     selPrime();
43     int n;
44     while(scanf("%d",&n)!=EOF)
45     {
46         int ans=Eular(n);
47         printf("%d
",ans);
48     }
49     return 0;
50 }

View Code

不筛素数也可以，代码如下：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 using namespace std;
 6 int Eular(int n)
 7 {
 8     int res=n;
 9     for(int i=2;i*i<=n;i++)
10     {
11         if(n%i==0)
12         {
13             res=res/i*(i-1);
14             while(n%i==0)n/=i;
15         }
16     }
17     if(n>1)res=res/n*(n-1);
18     return res;
19 }
20 int main()
21 {
22     int n;
23     while(scanf("%d",&n)!=EOF)
24     {
25         int ans=Eular(n);
26         printf("%d
",ans);
27     }
28     return 0;
29 }

View Code