品成人欧美大片久久国产欧美,国产成人综合久久精品尤物,2021国内精品久久久久久影院

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

這一題的關(guān)鍵在于如何快速地求出phi[n],剛開始的時(shí)候想過(guò)打表，可是10^6個(gè)數(shù)據(jù)，太大了，超代碼長(zhǎng)度。
后來(lái)借鑒了一下大牛們的算法，原來(lái)歐拉函數(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[]用來(lái)存放小于i的所有素?cái)?shù)，這里其實(shí)是一個(gè)模擬堆棧

//isprime[]用來(lái)標(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 閱讀(1675) 評(píng)論(0) 編輯收藏引用

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



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) 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)用)