欧拉函数（模板，相关问题持续更新中）

欧拉函数是一个很有用的东东。可以被扩展用来解决许多与素数相关的问题，逆元问题，欧拉函数降幂等！

概念：欧拉函数是小于或等于n（其实=时就是针对1的时候，1自身还是1）的正整数中与n互质的数的数目（特别地φ(1)=1），若n为质数可直接根据性质得出，否则的话要求解。

求解模板：

 1 int Euler(int n)
 2 {
 3     if(n==1) return 1;
 4     int ans=n;
 5     
 6     for(int i=2;i*i<=n;++i)
 7     {
 8         if(n%i==0)
 9         {
10             while(n%i==0) n/=i;
11             ans=ans/i*(i-1);
12         }
13     }
14     if(n!=1) ans=ans/n*(n-1);
15     
16     return ans;
17 }

欧拉定理：

费马小定理：当m是质数时，质数部分欧拉函数质数部分不用求了，直接用m-1代替就行！

所以，费马小定理就是当n为质数时欧拉定理的特殊情况！

欧拉函数求逆元：51nod1256（当然也可用扩展欧几里得，这里就不说了）

余数m为非质数时，跑一边欧拉函数，用欧拉定理变形求即可

余数m为质数时，欧拉函数直接=m-1，用费马小定理变形即可

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 typedef long long ll;
 6 int mod;
 7  
 8 int Qpow(llo a,llo b)
 9 {
10     int r=1;
11     while(b)
12     {
13         if(b&1)r=r*a%mod;
14         a=a*a%mod;
15         b>>=1;
16     }
17     
18     return r;
19 }
20 
21 int Euler(int n)
22 {
23     if(n==1) return 1;
24     int ans=n;
25     
26     for(int i=2;i*i<=n;++i)
27     {
28         if(n%i==0)
29         {
30             while(n%i==0) n/=i;
31             ans=ans/i*(i-1);
32         }
33     }
34     if(n!=1) ans=ans/n*(n-1);
35     
36     return ans;
37 }
38 
39 int main()
40 {
41     int a,b;
42     cin>>a>>b;
43     mod=b; 
44     
45     //llo ans=Qpow(a,mod-2);// mod质数
46     int ans=Qpow(a,Euler(mod)-1);
47     cout<<ans<<endl; 
48     
49     return 0;
50 }

欧拉函数还可判断是不是质数，因为质数欧拉值=p-1嘛！（当然可以用直接判断质数方法，这里只是为了说明欧拉函数有这个功能！）

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <iomanip>
 5 #include <map>
 6 #include <cstdio>
 7 #include <cstring>
 8 using namespace std;
 9 typedef long long ll;
10 typedef unsigned long long ull;
11 const int maxn=1e7+1;
12 int vis[maxn];
13 int n,m;
14 
15 int Euler(int n)
16 {
17     if(n==1) return 1;
18     int ans=n;
19 
20     for(int i=2;i*i<=n;++i)
21     {
22         if(n%i==0)
23         {
24             while(n%i==0) n/=i;
25             ans=ans/i*(i-1);
26         }
27     }
28     if(n!=1) ans=ans/n*(n-1);
29 
30     return ans;
31 }
32 
33 
34 int main()
35 {
36     ios::sync_with_stdio(false); cin.tie(0);
37 
38     cin>>n>>m;
39     while(m--)
40     {
41         int x;
42         cin>>x;
43 
44         int ans=Euler(x);
45         if(ans==x-1) cout<<"Yes"<<endl;
46         else cout<<"No"<<endl;
47     }
48 
49     return 0;
50 }

完。