Problem 1012 Relatives

来源:http://acm.fzu.edu.cn/problem.php?pid=1012

Problem Description
Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.

There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.

For each test case there should be single line of output answering the question posed above.

1
2
3
4
5
6
7
Sample Input
7
12
0
Sample Output
6
4

思路:这题是个欧拉函数.
当一个数 N = P1^Q1P2^Q2P3^Q3……PN^QN
那么 φ(N)=N
(p1-1)/p1(p2-1)/p2(p3-1)/p3….*(pn-1)/pn
代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
long long n;
int main() {
while (cin >> n && n!=0) {
long long q = n, a = n;
for (int i = 2; i*i <=a; i++) {
if (a%i == 0) {
q = q / i*(i - 1);
while (a%i == 0) a /= i;
}
}
if (a>1) q = q / a*(a - 1);
cout << q << endl;
}
return 0;
}