[11689] GCD(n, k) = 1

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

11689 - GCD(n, k) = 1

본문

자연수 $n$이 주어졌을 때, $\text{GCD}(n, k) = 1$을 만족하는 자연수 $1 \leq k \leq n$ 의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 $n$ ($1 \leq n \leq 10^{12}$)이 주어진다.

출력

$\text{GCD}(n, k) = 1$ 을 만족하는 자연수 $1 \leq k \leq n$ 의 개수를 출력한다.

제한

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

• $1 \leq N \leq 10^{12}$

---

풀이

설명을 참고 알고리즘으로 대체한다. 아예 문제에서 원하는 답을 함수 하나로 제공한다.

조절해야할 것은 어느 소수까지 계산해보아야 정답을 출력할 수 있냐는 점일 것이다. 입력으로 주어지는 숫자의 최댓값은 $10^{12}$이기 때문에, 그 숫자가 가질 수 있는 소수의 최댓값이 $x$라고 가정할 때, 그 수는 $\sqrt{10^{12}}$까지만 탐색해보면 소수인지 아닌지 판별할 수 있다. 이 수는 $1000000$ (1백만) 이므로 시간 안에 모두 계산할 수 있을 것이다.

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

코드

사용 언어 : C

최종 수정일 : 2023 / 2 / 3

#include <stdio.h>

typedef long long ll;

ll phi(ll x) {
    ll retval = 1;
    ll a = x;

    for (ll i = 2; i * i <= x; ++i) {
        if (i >= a) {
            break;
        }

        int divCount = 0;
        ll divRet = 1;
        while (a % i == 0) {
            ++divCount, divRet *= i;
            a /= i;
        }

        if (divCount > 0) {
            divRet /= i;
            retval *= (divRet * (i - 1));
        }
    }
    if (a > 1) {
        retval *= (a - 1);
    }

    return retval;
}

int main() {
    ll n;
    scanf("%lld", &n);
    printf("%lld", phi(n));
    return 0;
}