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;
}