The Fourth Dimension Space

枯葉北風寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢令

統計

隨筆 - 414
文章 - 13
評論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

友情鏈接

n皇后問題精彩分析
RMQ問題的精彩文章
開關燈問題

搜索

閱讀排行榜

評論排行榜

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 閱讀(1681) 評論(0) 編輯收藏引用

只有注冊用戶登錄后才能發表評論。




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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品