欧拉函数入门

欧拉函数：小于x的整数中与x互质的数的个数，一般用φ(x)表示，φ(1)=1

计算公式：φ(x)=x*(1-1/p1)(1-1/p2)...(1-1/pn)，其中x的所有素因子数分别为p1，p2，p3，...，pn.

常用性质：1.对于素数p，φ(p) = p-1， φ(p^k) = p^k-p^k-1

　　　　　2.当gcd(n,m) = 1时，φ(n*m) = φ(n) * φ(m).

暴力求一个数n的φ(n)模板

 1 /* */
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <string>
 7 using namespace std;
 8 
 9 //12==2*2*3;
10 int phi(int n)
11 {
12     int m=sqrt(n)+0.5;
13     int ans=n;
14     for(int i=2;i<=m;i++)
15     {
16         if(n%i==0)
17         {
18             ans=ans/i*(i-1);//即为ans*(1-1/i)
19             while( n%i==0 ) n/=i;//去重
20         }
21     }
22     if( n>1 ) ans=ans/n*(n-1);
23     return ans;
24 }
25 
26 int main()
27 {
28     int t;
29     scanf("%d",&t);
30     printf("%d
", phi(t));
31     return 0;
32 }

打表法：

 1 /* */
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <string>
 7 using namespace std;
 8 const int maxn=1000;
 9 int phi[maxn+10];
10 
11 void phi_init()
12 {
13     memset(phi,0,sizeof(phi));
14     phi[1]=1;
15     for(int i=2; i<=maxn; i++ )
16     {
17         if( !phi[i] )
18         {
19             for(int j=i; j<=maxn; j+=i )
20             {
21                 if( !phi[j] ) phi[j]=j;
22                 phi[j]=phi[j]/i*(i-1);
23             }
24         }
25     }
26 }
27 
28 int main()
29 {
30     phi_init();
31     for(int i=0; i<=10; i++ ) cout<<phi[i]<<" "<<endl;
32     return 0;
33 }

例题：Mathematically Hard

AC代码，由于数比较大记得用ull

 1 /* */
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cmath>
 5 #include <cstring>
 6 #include <string>
 7 using namespace std;
 8 const int maxn=5000010;
 9 typedef unsigned long long ull;
10 ull phi[maxn+10];
11 
12 void phi_init()
13 {
14     memset(phi,0,sizeof(phi));
15     phi[1]=1;
16     for(int i=2; i<maxn; i++ )
17     {
18         if( !phi[i] )
19         {
20             for(int j=i; j<maxn; j+=i )
21             {
22                 if( !phi[j] ) phi[j]=j;
23                 phi[j]=phi[j]/i*(i-1);
24             }
25         }
26     }
27 }
28 
29 void init()
30 {
31     ull temp=0;
32     int i;
33     phi[0]=0;
34     for(i=1; i<maxn; i++ )
35     {
36         temp += phi[i]*phi[i];
37         phi[i]=temp;
38     }
39 }
40 
41 int main()
42 {
43     int t, top=0, a, b;
44     scanf("%d",&t);
45     phi_init();
46     init();
47     while( t-- )
48     {
49         scanf("%d %d",&a,&b);
50         printf("Case %d: %llu
", ++top, phi[b]-phi[a-1]);
51     }
52     return 0;
53 }

View Code