Farey Sequence
Time Limit:1000MSMemory Limit:65536K
Total Submissions:13204Accepted:5181
Description
The Farey Sequence Fn for any integer n with n >= 2 is the set of irreducible rational numbers a/b with 0 < a < b <= n and gcd(a,b) = 1 arranged in increasing order. The first few areF2 = {1/2}F3 = {1/3, 1/2, 2/3}F4 = {1/4, 1/3, 1/2, 2/3, 3/4}F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}You task is to calculate the number of terms in the Farey sequence Fn.
Input
There are several test cases. Each test case has only one line, which contains a positive integer n (2 <= n <= 106). There are no blank lines between cases. A line with a single 0 terminates the input.
Output
For each test case, you should output one line, which contains N(n) —- the number of terms in the Farey sequence Fn.
Sample Input
23450
Sample Output
1359
Source
,Author:Mathematica@ZSU
简单的欧拉函数模板题。
所谓欧拉函数：对于一个正整数n，小于n且和n 互质的正整数（包括1 ）的个数，记做φ(n) 。
通式：φ(x)=x*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。
欧拉函数代码实现：
//直接求解欧拉函数int euler(int n){ //返回euler(n)int res=n,a=n;for(int i=2;i*i<=a;i++){if(a%i==0){res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出while(a%i==0) a/=i;}}if(a>1) res=res/a*(a-1);return res;}//筛选法打欧拉函数表 #define Max 1000001int euler[Max];void Init(){euler[1]=1;for(int i=2;i<Max;i++)euler[i]=i;for(int i=2;i<Max;i++)if(euler[i]==i)for(int j=i;j<Max;j+=i)euler[j]=euler[j]/i*(i-1);//先进行除法是为了防止中间数据的溢出 }本题就是欧拉函数的直接使用：#include<stdio.h>#include<string.h>#include<math.h>#define LL __int64#define Max 1005000LL sum[1005000];void init(){sum[1]=1;for(LL i=2;i<Max;i++)sum[i]=i;for(LL i=2;i<Max;i++)if(sum[i]==i)for(LL j=i;j<Max;j+=i)sum[j]=sum[j]/i*(i-1);}int main(){LL n;LL i,t;init();while(scanf("%I64d",&n)!=EOF){t=0;if(n==0)break;for(i=2;i<=n;i++)t+=sum[i];printf("%I64d\n",t);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，当你下定决心准备出发时，最困难的时刻就已经过去了。那么，出发吧。
