欧拉函数：HDU1787-GCD Again（欧拉函数的模板）

GCD Again

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 3702 Accepted Submission(s): 1640

Problem Description

Do you have spent some time to think and try to solve those unsolved problem after one ACM contest?

No? Oh, you must do this when you want to become a “Big Cattle”.

Now you will find that this problem is so familiar:

The greatest common divisor GCD (a, b) of two positive integers a and b, sometimes written (a, b), is the largest divisor common to a and b. For example, (1, 2) =1, (12, 18) =6. (a, b) can be easily found by the Euclidean algorithm. Now I am considering a little more difficult problem:

Given an integer N, please count the number of the integers M(0 < M < N)which satisfies (N,M)>1.

This is a simple version of problem “GCD” which you have done in a contest recently,so I name this problem “GCD Again”.If you cannot solve it still,please take a good think about your method of study.

Good Luck!

Input

Input contains multiple test cases. Each test case contains an integers N (1 < N < 100000000). A test case containing 0 terminates the input and this test case is not to be processed.

Output

For each integers N you should output the number of integers M in one line, and with one line of output for each line in input.

Sample Input

2

4

0

Sample Output

0

1

一.互质的概念：

1、定义

互质（relatively primeì）又叫互素。若N个整数的最大公因数是1，则称这N个整数互质。

例如8,10的最大公因数是2，不是1，因此不是整数互质。

7,10,13的最大公因数是1，因此这是整数互质。

5和5不互质，因为5和5的公因数有1、5。

1和任何数都成倍数关系，但和任何数都互质。因为1的因数只有1，而互质数的原则是：只要两数的公因数只有1时，就说两数是互质数。1只有一个因数（所以1既不是质数（素数），也不是合数），无法再找到1和其他数的别的公因数了，所以1和任何数都互质（除0外）。

互质数的写法：如c与m互质，则写作（c,m）=1。

小学数学教材对互质数是这样定义的：“公约数只有1的两个数，叫做互质数。”

这里所说的“两个数”是指自然数。

“公约数只有 1”，不能误说成“没有公约数。”

二.欧拉函数：

1.定义：

对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。例如euler(8)=4，因为1,3,5,7均和8互质。

2.说明：

Euler函数表达通式：euler(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…(1-1/pn),其中p1,p2……pn为x的所有素因数，x是不为0的整数。

(注意：每种质因数只一个。比如 12 = 2*2*3 那么 φ(12) = 12 * (1-1/2) * (1-1/3)=4 )

euler(1)=1（唯一和1互质的数（小于等于）就是1本身）。

欧拉函数性质： 1、 φ(mn) = φ(m) φ(n)

2、若n为奇数，φ(2n) = φ(n)。

欧拉公式的延伸：一个数的所有质因子之和是euler(n)*n/2。

注意：在欧拉函数中，函数值是 [ 1 , n ] 中与 n 互质数个数

其实关于欧拉函数数学不好的，实在看不懂公式的推导的可以直接去看公式理解代码，代码并不是很复杂，理解了之后也可以使用欧拉函数。

#include<bits/stdc++.h>

using namespace std;

//欧拉函数的标准模板

long long eular(long long n)

{

    long long ans = n;

    for(int i=2;i<=sqrt(n);i++)

    {

        if(n%i == 0)

        {

            n /= i;

            ans = ans/i*(i-1);

            while(n%i == 0)

                n /= i;

        }

    }

    if(n > 1)

        ans = ans/n*(n-1);

    return ans;

}

int main()

{

    long long n;

    while(scanf("%lld",&n) && n)

    {

        long long ans = eular(n);

        ans = n - ans - 1;

        printf("%lld\n",ans);

    }

    return 0;

}

巴特西