「POJ2478」Farey Sequence
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}
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 <= 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
|
1 2 3 4 5 |
2 3 4 5 0 |
Sample Output
|
1 2 3 4 |
1 3 5 9 |
题解
欧拉函数
phi(p^k)=(p-1)*p^(k-1)
phi(a*b)=phi(a)*phi(b)（a,b互质）
phi(p)=p-1（p为质数）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include<iostream> #include<cstdio> using namespace std; int n; int phi[1000005],pri[1000005],tot; long long ans; bool mark[1000005]; void getphi() { phi[1]=1; for(int i=2;i<=1000000;i++) { if(!mark[i]){pri[++tot]=i;phi[i]=i-1;} for(int j=1;j<=tot;j++) { int x=pri[j]; if(i*x>1000000)break; mark[i*x]=1; if(i%x==0){phi[i*x]=phi[i]*x;break;} else phi[i*x]=phi[i]*phi[x]; } } } int main() { getphi(); while(scanf("%d",&n)) { if(!n)break; ans=0; for(int i=2;i<=n;i++) ans+=phi[i]; printf("%lld\n",ans); } return 0; } |
Subscribe
计数器 9318799
OI 课件=>
OI 课件=>