poj2478 Farey Sequence 欧拉函数的应用

仔细看看题目,按照题目要求 其实就是 求 小于等于n的 每一个数的 欧拉函数值  的总和,为什么呢,因为要构成 a/b 然后不能约分  所以 gcd(a,b)==1,所以  分母 b的 欧拉函数值  就是 以b为分母的 这样的数有几个,分母b的范围 是小于等于n,所以 直接套一个模版就可以了 ,网上找的  说筛选的比较好,下面代码中有一个 注释掉的 模版 貌似 是错的,还不清楚为什么  弄清楚了 重新 注明一下 


#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set> #define ll long long
#define LL __int64
#define eps 1e-8 //const ll INF=9999999999999; #define inf 0xfffffff using namespace std; //vector<pair<int,int> > G;
//typedef pair<int,int> P;
//vector<pair<int,int>> ::iterator iter;
//
//map<ll,int>mp;
//map<ll,int>::iterator p;
//
//vector<int>G[30012]; #define N 1000012 //LL euler[N];
//int p[N][15];
//int num[N];
LL phi[N]; //void init()//这个模版现在不确定对不对,反正题目用不上
//{
// int i,j;
// euler[1]=1;
// for(i=2;i<N;i++)//筛选法得到数的素因子及每个数的欧拉函数值
// {
// if(!euler[i])
// {
// for(j=i;j<N;j+=i)
// {
// if(!euler[j])
// euler[j]=j;
// euler[j]=euler[j]*(i-1)/i;
// p[j][num[j]++]=i;
// }
// }
// euler[i]+=euler[i-1];
// }
//} void init()//筛选法求欧拉函数的模版 直接复制来的
{
memset(phi, 0, sizeof(phi));
phi[1] = 1;
for(int i = 2; i < N; i++) if(!phi[i])
{
for(int j = i; j < N; j+=i)
{
if(!phi[j]) phi[j] = j;
phi[j] = phi[j] / i * (i-1);
}
}
return ;
} int main(void)
{
init();
int n;
while(scanf("%d",&n),n)
{
LL ans=0;
for(int i=2;i<=n;i++)
ans+=phi[i];
printf("%I64d\n",ans);
}
}
上一篇:获取Excel数据(或部分数据)并导出成txt文本格式


下一篇:HTTP 返回状态消息讲解