POJ2478 Farey Sequence【快速求欧拉函数】

本文主要是介绍POJ2478 Farey Sequence【快速求欧拉函数】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给你一个数n，对于0 < a < b <= n，求真分数a/b的个数

解题思路：

因为a/b为真分数，所以a和b互质。

求真分数a/b的个数。其实就是求0 < i <= n中，小于i的正整数中，

有多少个与i互质的数。累加起来就是真分数a/b的个数。

其实就是欧拉函数

因为n的规模为10^6，可用快速求欧拉函数的方法求得（类似于筛法求素数）。

根据推论：设P是素数，
  若p是x的约数，则E(x*p)=E(x)*p.
  若p不是x的约数，则E(x*p)=E(x)*E(p)=E(x)*(p-1). 

根据筛法求素数的方法，由E(x)求得E（x*p）。

参考博文：http://www.cppblog.com/RyanWang/archive/2009/07/19/90512.html

AC代码：

#include<stdio.h>int prime[100010],phi[1000010];
bool unprime[1000010];
__int64 sum[1000010];void Euler()
{int i,j,k = 0;//phi[1] = 1;for(i = 2; i <= 1000000; i++){if(!unprime[i]){prime[k++] = i;phi[i] = i-1;}for(j = 0; j < k && prime[j]*i <= 1000000; j++){unprime[prime[j] *i] = true;if(i % prime[j] != 0){phi[prime[j]*i] = phi[i]*(prime[j]-1);}else{phi[prime[j]*i] = phi[i]*prime[j];break;}}}
}int main()
{int i,n;Euler();for(i = 1; i <= 1000000; i++)sum[i] = sum[i-1] + phi[i];while(~scanf("%d",&n) && n){printf("%I64d\n",sum[n]);}return 0;
}

这篇关于POJ2478 Farey Sequence【快速求欧拉函数】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---