Home [4355] 서로소
Post
Cancel

[4355] 서로소

문제 링크 : https://www.acmicpc.net/problem/4355

4355 - 서로소

본문

양의 정수 n이 주어졌을 때, n보다 작은 양의 정수 중에서 n과 서로소인 수 개수를 구하는 프로그램을 작성하시오.

두 정수 ab가 서로소가 되려면 x>1,y>0,z>0이면서, a=xy,b=xz를 만족하는 정수가 없어야 한다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 n1000000000으로 이루어져 있다.

입력의 마지막 줄에는 0이 주어진다.

출력

입력으로 주어진 n마다 n보다 작으면서 서로소인 양의 정수의 수를 출력한다.

제한

시간 제한메모리 제한
1sec128MB
  • 0<n1000000000 (109)

풀이

이제는 바로 깨달아보자. “서로소 = phi 함수”. 심지어 문제 내용도 GCD(n, k) = 1 (백준 11689) 문제와 똑같다. 그대로 구현하자.

대신 함정이 하나 있다. 바로 n=1인 경우. 11689번 문제에서는 GCD 값을 계산하는 것이었으므로 ϕ(1)=1이었지만, 이 문제에서는 n보다 작은 수들 중 서로소를 구해야하므로 ϕ(1)=0이다. 이것만 핸들링하면 답을 얻을 수 있다.

코드

사용 언어 : 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;
}
This post is licensed under CC BY 4.0 by the author.