久久久久综合网久久,99热精品久久只有精品,久久精品人妻中文系列

POJ 2478 Farey Sequence(歐拉函數的應用)

這一題的關鍵在于如何快速地求出phi[n],剛開始的時候想過打表，可是10^6個數據，太大了，超代碼長度。
后來借鑒了一下大牛們的算法，原來歐拉函數可以在打素數表的時候求出，這樣復雜度大約為n;

這個算法的核心，基于以下這個定理：
若(N%a==0 && (N/a)%a==0) 則有:E(N)=E(N/a)*a;
若(N%a==0 && (N/a)%a!=0) 則有:E(N)=E(N/a)*(a-1);

代碼如下：

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

//基于素數篩選法，計算歐拉函數phi[1] to phi[MAX],復雜度約為n，很快

//傳入三個數組:

//phi[]用于存放歐拉函數

//prime[]用來存放小于i的所有素數，這里其實是一個模擬堆棧

//isprime[]用來標志該數是不是素數，初始值為0

////////////////////BEGEIN_TEMPLATE_BY_ABILITYTAO_ACM/////////////////////////

#define MAX 1000000

__int64 phi[MAX+1]={0};

__int64 prime[MAX+1]={0};

bool isprime[MAX+1]={0};

void get_phi()//這是一個基于素數篩選的線性算法，很快

{

__int64 i,j;

__int64 len=0;

for(i=2;i<=MAX;i++)

{

if(isprime[i]==false) //false代表是質數

{

prime[++len]=i;

phi[i]=i-1;

}

for(j=1;j<=len&&prime[j]*i<=MAX;j++)

{

isprime[prime[j]*i]=true;//true代表是合數

if(i%prime[j]==0)

{

phi[i*prime[j]]=phi[i]*prime[j];

break;

}

else

phi[i*prime[j]]=phi[i]*(prime[j]-1);

}

/////////////////////END_TEMPLATE_BY_ABILITYTAO_ACM///////////////////////////////

__int64 s[MAX];

int main()

{

__int64 i;

phi[1]=0;

get_phi();

for(i=2;i<=MAX;i++)

s[i]=s[i-1]+phi[i];

while(1)

{

scanf("%I64d",&i);

if(i==0) break;

printf("%I64d\n",s[i]);

}

return 0;

}

get_phi函數中的i*prime[j]相當于N，prime[j]相當于a,i相當于N/a;

posted on 2009-10-30 13:41 abilitytao 閱讀(1671) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

POJ 2478 Farey Sequence(歐拉函數的應用)