The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

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 阅读(1670) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理