[4355] 서로소

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

4355 - 서로소

본문

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

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

입력

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

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

출력

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

제한

시간 제한	메모리 제한
1sec	128MB

• $0<n\le 1000000000$ (${10}^9$)

---

풀이

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

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

• 참고 알고리즘 : 오일러 phi 함수

코드

사용 언어 : C

최종 수정일 : 2023 / 2 / 27

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