国产精品美女久久久久aⅴ国产馆,激情六月婷婷久久,国产精品家庭影院

POJ 2478 Farey Sequence(歐拉函數(shù)的應(yīng)用)

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

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

//傳入三個數(shù)組:

//phi[]用于存放歐拉函數(shù)

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

//isprime[]用來標志該數(shù)是不是素數(shù)，初始值為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()//這是一個基于素數(shù)篩選的線性算法，很快

{

__int64 i,j;

__int64 len=0;

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

{

if(isprime[i]==false) //false代表是質(zhì)數(shù)

{

prime[++len]=i;

phi[i]=i-1;

}

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

{

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

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函數(shù)中的i*prime[j]相當于N，prime[j]相當于a,i相當于N/a;

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

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



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

The Fourth Dimension Space

導(dǎo)航

統(tǒng)計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

POJ 2478 Farey Sequence(歐拉函數(shù)的應(yīng)用)