아이디어

• 문제에 나온 "GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수"를 오일러 피(phi) 함수 $\varphi(n)$이라 한다. 이에 대한 설명은 나무위키 등에 자세하게 나와 있지만, 주요한 성질을 정리해보고 가자.

  • i) 소수 $p$에 대해 $\varphi(p^n) = p^{n-1}(p-1)$이다.
    • $p^n$은 $p$의 거듭제곱만을 인수로 가지므로, 어떤 자연수 $m$에 대해 $\gcd(m, p^n)$는 $m$이 $p$의 배수일 때 $p$가 되고, 그렇지 않을 때는 $1$이 될 것이다. 따라서 $\varphi(p^n)$는 $p^n$에서 $p$의 배수의 개수를 뺀 $p^n - \frac{p^{n}}{p}=p^{n-1}(p-1)$임을 알 수 있다.
  • ii) 서로소인 자연수 $a$, $b$에 대해 $\varphi(ab) = \varphi(a) \varphi(b)$이다.

• 그러므로 $n$을 소인수분해한 다음에, 각 소인수와 지수에 대해 i)를 적용하고, 이를 모두 곱하면 된다.

• 소인수분해를 하기 위해서는 소수 리스트가 필요한데, $n$의 최댓값이 $10^{12}$이므로 $n$ 이하의 소수를 모두 구해놓는 것은 불가능하다. 그러나, $n$이 소수가 아닐 때 $\sqrt{n}$ 이하의 소인수를 1개 이상 가진다는 점을 이용하면 $\sqrt{n}$의 길이의 리스트만 보는 것으로 소수를 판별할 수 있다. 그러므로 $\sqrt{10^{12}}=10^6$ 이하의 범위에서만 소수를 찾아놓자.

  • 만약 리스트 내의 어떤 소수로도 $n$이 나뉘어지지 않았다면 $n$은 소수이므로 i)에 의해 $\varphi(n)=n-1$을 반환한다.

  • 적당한 소인수로 나눈 뒤에도 $10^6$보다 큰 자연수 $R$이 남아버려 더 이상 소인수분해가 불가능할 때에는, 성질 ii)를 이용해 재귀적으로 $\varphi(R)$를 구해 구하던 결과에 곱하기로 하자. 이 재귀는 많아야 1번만 실행될 것이다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));

    static final int M = 1_000_000;   // sqrt of max N(10^12)
    static boolean[] isPrime = new boolean[M+1];
    static long n;

    public static void main(String[] args) throws Exception {
        // use Eratosthenes' sieve
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i=2; i <= M; i++) {
            if (isPrime[i]) {
                for (int j=i*2; j <= M; j += i) isPrime[j] = false;
            }
        }

        n = Long.parseLong(rd.readLine());
        System.out.println(phi(n));
    }

    // 1. for prime number p: phi(p^n) = p^n - p^(n-1) = p^(n-1) * (p-1)
    // 2. for coprime natural numbers a, b: phi(ab) = phi(a) * phi(b)
    static long phi(long n) {
        if (n == 1) return 1;

        long ret = 1;
        long m = n;
        boolean isNPrime = true;
        for (int i=2; i<=Math.min(n, M); i++) {
            if (!isPrime[i]) continue;
            int x = 0;
            while (m % i == 0) {
                x++;
                m /= i;
                isNPrime = false;
            }
            if (x > 0) {
                // multiply p^(x-1) * (p - 1)
                for (int j = 0; j < x-1; j++) ret *= i;
                ret *= i - 1;
            }
        }
        if (isNPrime)
            return n-1;
        return ret * phi(m);
    }
}

메모리 및 시간

• 메모리: 16484 KB
• 시간: 184 ms

리뷰

• 수 학 시 러
• 테스트케이스를 가능한 많이 찾아봐야했다. 특히 디버깅에 유용했던 테스트케이스 몇 개를 남겨놓는다.
  • $1\ 000\ 003$: $10^6$보다 큰 최소의 소수
  • $2\ 000\ 006$: $10^6$보다 큰 최소의 소수와 다른 소수의 곱
  • $9\ 999\ 999 \ 983$: 범위 한계에 가까운 수, $10^6$보다 큰 소인수를 포함한다.