Drolca

Apologize To Drolca
随笔 - 28, 文章 - 1, 评论 - 6, 引用 - 0
数据加载中……

pku 2478 Farey Sequence 欧拉函数

#include <iostream>
using namespace std;

const int size=1000005;
bool ok[size];
int ph[size];
int prime[size];
__int64 sum[size];
int pn;
int n;
void getph()
{
    int i,j;
    pn=0;
    for(i=2;i<size;i++)
    {
        if(!ok[i])
        {
            prime[pn++]=i;
            ph[i]=i-1;
        }
        for(j=0;(j<pn)&&(i*prime[j]<size);j++)
        {
            ok[i*prime[j]]=1;
            if((i%prime[j])==0)
            {
                ph[i*prime[j]]=ph[i]*prime[j];
                break;
            }
            else
                ph[i*prime[j]]=ph[i]*(prime[j]-1);

        }
    }
}
int main()
{
    ph[1]=1;
    getph();
    for(int i=2;i<size;i++)
        sum[i]=sum[i-1]+ph[i];
    while(scanf("%d",&n)!=EOF&&(n!=0))
        printf("%I64d\n",sum[n]);
    return 0;
}

posted on 2009-09-18 13:20 Drolca 阅读(191) 评论(0)  编辑 收藏 引用


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