GCD Again
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2611 Accepted Submission(s): 1090
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!
2
4
0
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<stdio.h> int euler(int n)//欧拉函数
{
int res=n,i;
for(i=2;i*i<=n;i++)
{
if(n%i==0)
res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出
while(n%i==0)
n/=i;//保证n一定是素数
}
if(n>1)
res=res/n*(n-1);
return res;
} int main()
{
int n;
while(scanf("%d",&n)&&n!=0)
printf("%d\n",n-euler(n)-1);//题目要求小于n，故还要减去1
return 0;
}