POJ 2478-Farey Sequence（欧拉函数）

亦凉 2022-08-21 01:25 20阅读 0赞

Farey Sequence

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;14071</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;5567</td> 
  </tr> 
 </tbody> 
</table>

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:Mathematica@ZSU

题意：

给定一个数n，求所有小于等于n的正整数中，有多少对是互质的。

知识点：

欧拉函数。

可以先套欧拉函数模板，然后从1-n枚举，依次使用欧拉函数求出值然后相加。

就像下面这样：

#include<iostream>
    using namespace std;
    
    int oula(int n)
    {
        int i,ans=n;
        for(i=2; i*i<=n; ++i)
            if(n%i==0)
            {
                ans-=ans/i;
                while(n%i==0)
                    n/=i;
            }
        if(n>1)
            ans-=ans/n;
        return ans;
    }
    
    int main()
    {
        int n,i;
        while(cin>>n&&n)
        {
            int ans=0;
            for(i=2; i<=n; ++i)
                ans+=oula(i);
            cout<<ans<<endl;
        }
    
        return 0;
    }

但是！！！这种方法会超时！！

由于这种情况下频繁的使用欧拉函数，所以需要预先打表。

所以，我们要使用递推求欧拉函数的方法。

预先把所有数的欧拉函数值都置为它本身，定理：如果p是一个正整数而且满足φ（p）=p-1，则这个数是素数。

在遍历过程中如果遇到与自身相等的情况，那么说明该数为素数，改变这个数的欧拉函数值，同时也能把该素因子整除的数改变。其复杂度为O（nlnn）。

AC代码如下：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const long long N=1000000;
    long long a[N+5];
    
    int main()
    {
        int n,i,j;
        for(i=1; i<=N; ++i)
            a[i]=i;
        for(i=2; i<=N; i+=2)
            a[i]/=2;
        for(i=3; i<=N; i+=2)
            if(a[i]==i)
                for(j=i; j<=N; j+=i)
                    a[j]=a[j]/i*(i-1);
        for(i=3; i<=N; ++i)
            a[i]+=a[i-1];
        while(~scanf("%d",&n)&&n)
            printf("%lld\n",a[n]);
        return 0;
    }

[POJ Contest]: http://poj.org/searchproblem?field=source&key=POJ+Contest