GCD Again |
| Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) |
| Total Submission(s): 193 Accepted Submission(s): 112 |
|
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 |
|
Sample Output
0 |
|
Author
lcy
|
|
Source
2007省赛集训队练习赛（10）_以此感谢DOOMIII
|
|
Recommend
lcy
|
/*
题意：给出你一个数n，然后让你求出比n小的，并且不与n互质的数的个数 初步思路：欧拉函数，用n减去欧拉函数-1
*/
#include<bits/stdc++.h>
using namespace std;
/**************************欧拉函数模板*****************************/
int euler(int n){
int cur=n,i;
for(i=;i*i<=n;i++){
/*
怎么样保证每一个能被n整除的数都是素因子呐，比当前i大的数，肯定能找到一个素数，相乘等于n
那么只需要每找到一个素数就把n中所有能和这个素数相乘等于n的数全部去除掉，那么这样就能满足
要求了。
*/
if(n%i==){
cur=cur-cur/i;
while(n%i==)
n/=i;
}
}
if(n>) cur=cur-cur/n;
return cur;
}
/**************************欧拉函数模板*****************************/
int n;
int main(){
// freopen("in.txt","r",stdin);
while(scanf("%d",&n)!=EOF&&n){
printf("%d\n",n-euler(n)-);
}
return ;
}