10820 Send a Table（欧拉函数）

Problem A

Send a Table

Input: Standard Input

Output: Standard Output

When participating in programming contests, you sometimes face the following problem: You know how to calcutale the output for the given input values, but your algorithm is way too slow to ever pass the time limit. However hard you try, you just can't discover the proper break-off conditions that would bring down the number of iterations to within acceptable limits.

Now if the range of input values is not too big, there is a way out of this. Let your PC rattle for half an our and produce a table of answers for all possible input values, encode this table into a program, submit it to the judge, et voila: Accepted in 0.000 seconds! (Some would argue that this is cheating, but remember: In love and programming contests everything is permitted).

Faced with this problem during one programming contest, Jimmy decided to apply such a 'technique'. But however hard he tried, he wasn't able to squeeze all his pre-calculated values into a program small enough to pass the judge. The situation looked hopeless, until he discovered the following property regarding the answers: the answers where calculated from two integers, but whenever the two input values had a common factor, the answer could be easily derived from the answer for which the input values were divided by that factor. To put it in other words:

Say Jimmy had to calculate a function Answer(x, y) where x and y are both integers in the range [1, N]. When he knows Answer(x, y), he can easily derive Answer(k*x, k*y), where k is any integer from it by applying some 易做图 calculations involving Answer(x, y) and k. For example if N=4, he only needs to know the answers for 11 out of the 16 possible input value combinations: Answer(1, 1), Answer(1, 2), Answer(2, 1), Answer(1, 3), Answer(2, 3), Answer(3, 2), Answer(3, 1), Answer(1, 4), Answer(3, 4), Answer(4, 3) and Answer(4, 1). The other 5 can be derived from them (Answer(2, 2), Answer(3, 3) and Answer(4, 4) from Answer(1, 1), Answer(2, 4) from Answer(1, 2), and Answer(4, 2) from Answer(2, 1)). Note that the function Answer is not symmetric, so Answer(3, 2) can not be derived from Answer(2, 3).

Now what we want you to do is: for any values of N from 1 upto and including 50000, give the number of function Jimmy has to pre-calculate.

Input

The input file contains at most 600 lines of inputs. Each line contains an integer less than 50001 which indicates the value of N. Input is terminated by a line which contains a zero. This line should not be processed.

Output

For each line of input produce one line of output. This line contains an integer which indicates how many values Jimmy has to pre-calculate for a certain value of N.

Sample Input Output for Sample Input

题意：给定一个n，求出1-n之内的互质组。

思路：欧拉函数。

φ函数的值　通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如12=2*2*3

欧拉公式

那么φ（12）=12*（1-1/2）*(1-1/3)=4

若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。

设n为正整数，以 φ(n)表示不超过n且与n互

素的正整数的个数，称为n的欧拉函数值，这里函数

φ：N→N，n→φ(n)称为欧拉函数。

欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。

特殊性质：当n为奇数时，φ(2n)=φ(n), 证明与上述类似。

注意加上1,1这种情况。

代码：

#include <stdio.h>  
#include <string.h>  
#include <math.h>  
const int MAXN = 50005;  
  
int n, sum[MAXN], i, out;  
  
int save(int n) {  
    int num = n;  
    int m = sqrt(num), ans = num;  
    for (int i = 2; i <= m && i <= num; i ++) {  
        if (num % i == 0) {  
            ans = (ans - ans / i);  
            while (num % i == 0) {  
                num /= i;  
            }  
        }  
    }  
    if (num != 1) {  
        ans = (ans - ans / num);  
    }  
    return ans;  
}  
  
int main() {  
    for (i = 2; i <= 50001; i ++) {  
        sum[i] = save(i);  
    }  
    while (~scanf("%d", &n) && n) {  
        out = 1;  
        for (i = 2; i <= n; i ++) {  
            out += sum[i] * 2;  
        }  
        printf("%d\n", out);  
    }  
    return 0;  
}

补充：软件开发 , C++ ,