Farey Sequence

題意：給定一個數(shù)n，求在[1,n]這個范圍內(nèi)兩兩互質(zhì)的數(shù)的個數(shù)。（轉(zhuǎn)化為給定一個數(shù)n，比n小且與n互質(zhì)的數(shù)的個數(shù)）

?

知識點(diǎn)：

歐拉函數(shù)：

普通求法：

int Euler(int n) {int ans=n;for(int i=0;i<cnt&&prime[i]<=n;i++){if(n%prime[i]==0){ans=ans-ans/prime[i];while(n%prime[i]==0)n/=prime[i];}}if(n==1)return ans;if(n>1)return ans-ans/n;}

篩選法：（基于素數(shù)篩，跟著代碼模擬一遍就懂）

void Init() { for(int i=1;i<N;i++)euler[i]=i;for(int i=2;i<N;i++) //i=1時，euler[1] 不變if(euler[i]==i)for(int j=i;j<N;j+=i)euler[j]=euler[j]/i*(i-1); }

?

題解：篩選法求歐拉函數(shù)

#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=1e6+5;int euler[N];void Init() {euler[1]=1;for(int i=2;i<N;i++)euler[i]=i;for(int i=2;i<N;i++)if(euler[i]==i)for(int j=i;j<N;j+=i)euler[j]=euler[j]/i*(i-1); }int main() {Init();int n;while(cin>>n&&n){long long ans=0;for(int i=2;i<=n;i++)ans+=euler[i];cout<<ans<<endl;} }

?

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/shentr/p/5317442.html

總結(jié)

以上是生活随笔為你收集整理的poj2478 Farey Sequence (欧拉函数)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。