您好,登錄后才能下訂單哦!
這篇文章將為大家詳細講解有關(guān)歐拉函數(shù)有什么用,小編覺得挺實用的,因此分享給大家做個參考,希望大家閱讀完這篇文章后可以有所收獲。
題解:就是求n以內(nèi) 所有互素的數(shù) 的組合數(shù)! 即n以內(nèi)所有整數(shù)的歐拉函數(shù)之和!
歐拉函數(shù)知識點 可以參考白書。
// 2478 Accepted 4084K 235MS C++ 620B // 2478 Accepted 8000K 282MS C++ 735B #include <iostream>//詳細可以參見 白書! #include<cstdio> #include<cstring> using namespace std; #define N 1000010 int phi[N]; void Eula() { int i,j; memset(phi,0,sizeof(phi));//篩法 求出N以內(nèi)的所有 n以內(nèi)的互素數(shù)! for(i=2;i<=N;i++)//素數(shù)從2開始 { if(!phi[i]) { for(j=i;j<=N;j+=i) { if(!phi[j]) phi[j]=j;//賦給該數(shù) 素因子分解后 它的最小素因子! phi[j]=phi[j]/i*(i-1);//后面每一個素因子可以組成的數(shù) 都用公式刷新下該數(shù)的 歐拉數(shù)! } } } //for(i=2;i<=N;i++)phi[i]+=phi[i-1]; 第二種方法可以把所有答案打好表! } int main() { Eula(); int n,i; __int64 sum; while(scanf("%d",&n),n) { sum=0; for(i=2;i<=n;i++) sum+=phi[i]; printf("%I64d\n",sum); } return 0; }
上面是打表的方法--適用于多數(shù)據(jù) 而數(shù)據(jù)??;
以下為求單個 數(shù)的歐拉函數(shù)--適用于大數(shù)據(jù) 小規(guī)模;
#include<stdio.h> long long phi(long long a) { long long temp=a; for(long long i=2;i*i<=a;i++) if(a%i==0) { while(!(a%i))a/=i; //該數(shù)有此素因子,先除完. temp=temp/i*(i-1); //利用公式 n/(1-1/p); } if(a!=1) //最后a不是1 就是一個素數(shù). temp=temp/a*(a-1);//再利用公式除一下就ok! return temp; } int main() { long long a,b,c; while(scanf("%lld",&a)!=EOF) printf("%lld\n",phi(a)); return 0; }
關(guān)于“歐拉函數(shù)有什么用”這篇文章就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,使各位可以學(xué)到更多知識,如果覺得文章不錯,請把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。