国产精品gz久久久,久久九九亚洲精品,久久夜色精品国产噜噜亚洲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[]用來標(biāo)志該數(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]相當(dāng)于N，prime[j]相當(dāng)于a,i相當(dāng)于N/a;

posted on 2009-10-30 13:41 abilitytao 閱讀(1675) 評論(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)用)