歐拉函數模板

一、單個歐拉函數計算

可評測鏈接：http://codevs.cn/problem/4939/

單個歐拉函數計算公式：φ（n）=n*（1-1/p1）*（1-1/p2）*……*（1-1/pn）

Step 1：

一邊分解質因數一邊算，時間復雜度O（n）

#include<cstdio>
using namespace std;
long long n,ans;
int main()
{while(1){scanf("%lld",&n);if(!n) break;ans=n;for(long long i=2;i<=n;i++)if(n%i==0){while(n%i==0) n/=i;ans=ans/i*(i-1);}printf("%lld\n",ans);}
}

Step 2 :

性質：合數至少有一個不大于不大于根號n的素因子

所以循環只需循環到根號n即可 時間復雜度 O(根號n)

#include<cstdio>
using namespace std;
long long n,ans;
int main()
{while(1){scanf("%lld",&n);if(!n) break;ans=n;for(long long i=2;i*i<=n;i++)if(n%i==0){while(n%i==0) n/=i;ans=ans/i*(i-1);}if(n>1) ans=ans/n*(n-1);printf("%lld\n",ans);}
}

Step 3：

素數除了2之外都是奇數，

所以單獨處理2，然后之枚舉根號n以內的奇數

時間復雜度 O[（根號n）/2]

#include<cstdio>
using namespace std;
int main()
{long long n,ans;while(1){scanf("%lld",&n);if(!n) return 0;ans=n;if(n%2==0){while(n%2==0) n/=2;ans=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);printf("%lld\n",ans);}
}

?

二、歐拉篩

歐拉篩可以快速求[1,n]內所有數的歐拉函數，所以在涉及歐拉函數求和時會使用

?利用性質：

如果i%p==0，那么φ（i*p）=φ（i）*p

如果i%p！=0，那么 φ（i*p）=φ（i）*（p-1） ? 其中p為質數

代碼為求2——n的歐拉函數之和

評測鏈接：http://poj.org/problem?id=2478

時間復雜度：O（n）

#include<cstdio>
#define N 1000001 
using namespace std;
bool check[N];
int prime[N],cnt,phi[N],a;
long long sum[N];
void euler()
{phi[1]=1;for(int i=2;i<=N;i++){if(!check[i]){prime[++cnt]=i;phi[i]=i-1;}for(int j=1;j<=cnt;j++){if(i*prime[j]>N) break;check[i*prime[j]]=true;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}phi[i*prime[j]]=phi[i]*(prime[j]-1);}}
}
int main()
{euler();for(int i=1;i<=N;i++) sum[i]+=sum[i-1]+1ll*phi[i];while(1){scanf("%d",&a);if(!a) return 0;printf("%lld\n",sum[a]-1);}
}

?

三、埃氏篩法

埃氏篩法可以O（1）查詢i是否與n互質，在涉及 查詢與n互質的數是什么 時 會使用

時間復雜度：O（nlog2n）

下方代碼為求與n互質的第k個數

評測鏈接：http://poj.org/problem?id=2773

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
bool check[1000001];
int euler(int n)//埃氏篩法模板 
{int m=int(sqrt(n+0.5));int ans=n,k=n;memset(check,0,sizeof(check));for(int i=2;i<=m;i++)if(n%i==0){ans=ans/i*(i-1);for(int j=1;i*j<=k;j++)check[i*j]=true;while(n%i==0) n/=i;}if(n>1){ans=ans/n*(n-1);for(int j=1;n*j<=k;j++) check[n*j]=true;}return ans;
}
int main()
{int m,k,ans,cnt,t,i;while(scanf("%d%d",&m,&k)!=EOF){ans=euler(m);cnt=0;if(k%ans==0) t=k/ans-1;else t=k/ans;k=k-ans*t;for(i=1;i<=m;i++){if(!check[i]) cnt++;if(cnt==k) break;}printf("%d\n",i+m*t);}
}

?

?