4355 - 서로소
본문
양의 정수
두 정수
입력
입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는
입력의 마지막 줄에는
출력
입력으로 주어진
제한
시간 제한 | 메모리 제한 |
---|---|
1sec | 128MB |
( )
풀이
이제는 바로 깨달아보자. “서로소 = phi 함수”. 심지어 문제 내용도 GCD(n, k) = 1 (백준 11689) 문제와 똑같다. 그대로 구현하자.
대신 함정이 하나 있다. 바로
- 참고 알고리즘 : 오일러 phi 함수
코드
사용 언어 : C
최종 수정일 : 2023 / 2 / 27
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
int solve(int x) {
if (x == 1) {
return 0;
}
int retval = 1;
for (int i = 2; i * i <= x; ++i) {
int cnt = 0;
int pi = 1;
while (x % i == 0) {
++cnt;
x /= i, pi *= i;
}
if (cnt > 0) {
retval *= (pi - pi / i);
}
}
if (x > 1) {
retval *= (x - 1);
}
return retval;
}
int main() {
while (true) {
int n;
scanf("%d", &n);
if (n == 0) {
break;
}
printf("%d\n", solve(n));
}
return 0;
}