poj 2478 Farey Sequence 欧拉函数递推打表

最新推荐文章于 2021-08-04 15:15:41 发布

ctrss

最新推荐文章于 2021-08-04 15:15:41 发布

阅读量326

点赞数

分类专栏： acm 数论欧拉函数文章标签： acm 数论欧拉函数 poj

本文链接：https://blog.csdn.net/ctrss/article/details/51213127

版权

acm 同时被 3 个专栏收录

33 篇文章

订阅专栏

数论

7 篇文章

订阅专栏

欧拉函数

5 篇文章

订阅专栏

Farey Sequence

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 14434		Accepted: 5719

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

题意：求f(n)中数的个数。

思路：可以看出f(n)=f(n-1)+phi(n)（法雷数列中分母为n的项，其分子与其互质，所以分母为n的数的个数即为phi(n)），打表求出1e6内的欧拉函数，累加即可

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
long long p[1000006];
void phi(long long N)    
{    
    for(long long i=1; i<N; i++)  p[i] = i;    
    for(long long i=2; i<N; i+=2) p[i] >>= 1;    
    for(long long i=3; i<N; i+=2)    
    {    
        if(p[i] == i)    
        {    
            for(long long j=i; j<N; j+=i)    
                p[j] = p[j] - p[j] / i;    
        }    
    }    
}    
int main(int argc, char const *argv[])
{   long long i,j,k,m,n,t;
	long long sum=0;
	phi(1000001);
    while(~scanf("%lld",&n))
    {   sum=0;
    	if(n==0)break;
    	for(i=2;i<=n;i++)sum+=p[i];
    	printf("%lld\n",sum);	

    }
	return 0;
}