唯一分解定理：合数N=p 1 k 1 ∗ p 2 k 2 ∗ p 3 k 3 . . . . ∗ p k k k p1^k1^*p2^k2^*p3^k3^....*pk^kkp1k1∗p2k2∗p3k3....∗pkkk
欧拉函数:找到1 − N 中 与 N 互 质 的 数 ， （ 1 与 任 何 数 互 质 ） 1-N中与N互质的数，（1与任何数互质）1−N中与N互质的数，（1与任何数互质）
ϕ ( N ) = N × ( p 1 − 1 / p 1 ) × ( p 2 − 1 / p 2 ) × … × ( p m − 1 / p m ) ϕ(N) = N×(p1−1/p1)×(p2−1/p2)×…×(pm−1/pm)ϕ(N)=N×(p1−1/p1)×(p2−1/p2)×…×(pm−1/pm)=N× \times×( 1 − 1 / p 1 ) (1-1/p1)(1−1/p1)× \times×( 1 − 1 / p 2 ) (1-1/p2)(1−1/p2)…( 1 − 1 / p k ) (1-1/pk)(1−1/pk)
时间复杂度：O ( n ) O(\sqrt[]n)O(n)
#include<bits/stdc++.h> using namespace std; const int N=1e5; int main() { int t; cin>>t; while(t--) { int a; cin>>a; int res=a; for(int i=2;i<=a/i;i++) { if(a%i==0) { while(a%i==0) a/=i; res=res/i*(i-1); } } if(a>1) res=res/a*(a-1); cout<<res<<endl; } }
利用欧拉筛求欧拉函数之和
时间复杂度:O ( n ) O(n)O(n)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10; int prime[N]; bool f[N]; ll phi[N]; int n; int cnt; ll get_euler(int x) { f[1]=1; phi[1]=1; for(int i=2;i<=n;i++) { if(!f[i]) { prime[cnt++]=i; phi[i]=i-1; } for(int j=0;prime[j]<=n/i&&j<cnt;j++) { f[prime[j]*i]=1; if(i%prime[j]==0) { phi[prime[j]*i]=phi[i]*prime[j]; break; } phi[prime[j]*i]=phi[i]*(prime[j]-1); } } ll res=0; for(int i=1;i<=n;i++) { res+=phi[i]; } return res; } int main() { cin>>n; cout<<get_euler(n)<<endl; }
#include <bits/stdc++.h> using namespace std; int t,a,b; int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1,y=0; return a; } int d,x1,y1; d=exgcd(b,a%b,x1,y1); x=y1; y=x1-a/b*y1; return d; } int main() { scanf("%d",&t); while(t--) { int a,b,m; scanf("%d%d%d",&a,&b,&m); int x,y; int d=exgcd(a,-m,x,y); if(b%d) cout<<"impossible\n"; else cout<<1LL*(b/d)*x%m<<endl; } }
