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;
}