2478_打码高手怎么日赚几百_云赚打码一天能赚多少

poj2478 又一欧拉公式的运用

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 <= 106). There are no blank lines between cases. A line with a single 0 terminates the input.

Output

Sample Input

2
3
4
5
0

Sample Output

1
3
5
9

题目大意就是求Fi集合中元素的个数，其中Fi集合的元素满足下列条件

形如a/b，且0<a<b<=i, gcd(a,b)=1

很明显，这题就是欧拉公式的运用，关于欧拉公式可查看下这篇文章

对于这题，可以先求出以每一个小于m的数为分母的数的个数，即也是与该数互素的数的个数，也就是求的phi[i]；

然后再每一个phi都加起来

题目就是比较简单的欧拉运用，1A

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/shouji/article-23179-1.html