The Fourth Dimension Space

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

這個(gè)算法的核心，基于以下這個(gè)定理：
若(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;

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

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

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

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

//isprime[]用來標(biāo)志該數(shù)是不是素?cái)?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()//這是一個(gè)基于素?cái)?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 閱讀(1681) 評(píng)論(0) 編輯收藏引用

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




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

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

The Fourth Dimension Space

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

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