POJ 2478

Farey Sequence

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 11772		Accepted: 4585

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⁶). 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

Sample Output

Source

POJ Contest,Author:Mathematica@ZSU

题目题意很明白，思路也很清晰

用欧拉函数去做就是

问题在于总是超时

直接euler_phi()

 1 void euler_phi(int n)
 2 {
 3     memset(phi,0,sizeof(phi));
 4     phi[1] = 1;
 5     for(int i=2;i<=n;i++)
 6     {
 7         int ans=i;
 8         int h = i;
 9         int m = sqrt(i+0.5);
10         if(h % 2 ==0)
11         {
12             ans = ans/2;
13             while(h%2==0)
14                 h/=2;
15         }
16         for(int j=2;j<=m;j+=2)
17         {
18             if(h%j==0)
19             {
20                 ans=ans/j*(j-1);
21                 while(h%j==0)h/=j;
22              }
23          }
24         if(h>1)ans=ans/h*(h-1);
25         phi[i]=ans;
26     }
27 }

超时

然后看最短用时16ms = =

天惹

可以先把素数求出来

然后再求欧拉函数

不知道为什么好像我的被我写得更慢了

找到一个直接求欧拉函数就过了的

看了好久才看懂

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cmath>
 4 using namespace std;
 5 const int maxn=1000001;
 6 int phi[maxn];
 7 
 8 void getphi(){//这里算法减少了一个while循环
 9     memset(phi,0,sizeof(phi));
10     phi[1]=1;
11     for(int i=2;i<maxn;i++){
12         if(phi[i]==0){
13             for(int j=i;j<maxn;j+=i){
14                 if(phi[j]==0)
15                     phi[j]=j;
16                 phi[j]=phi[j]/i*(i-1);
17             }
18         }
19     }
20 }
21 int main(){
22     getphi();
23     int n;
24     while(cin>>n&&n){
25         long long sum=0;
26         for(int i=2;i<=n;i++){
27             sum+=(long long)phi[i];
28         }
29        cout<<sum<<endl;
30     }
31     return 0;
32 }

相关推荐