Farey Sequence
Time Limit: 1000MS | Memory Limit: 65536K |
Total Submissions: 7076 | Accepted: 2610 |
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 are
F2 = {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 <= 10 6). 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
2
3
4
5
0
Sample Output
1
3
5
9
Source
POJ Contest,Author:[email protected]
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
//基于素数筛选法,计算欧拉函数phi[1] to phi[MAX],复杂度约为n,很快
//传入三个数组:
//phi[]用于存放欧拉函数
//prime[]用来存放小于i的所有素数,这里其实是一个模拟堆栈
//isprime[]用来标志该数是不是素数,初始值为0
/*
这个算法的核心,基于以下这个定理:
若(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);
*/
#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;
}