[백준] 11689: GCD(n, k) = 1 (Java)

NNIJGNUS·2025년 10월 5일

Java ps 백준 수학 오일러 피 함수 정수론

문제

아이디어

자연수 N이 주어졌을때, N보다 작고 서로소인 자연수의 개수를 구하는 간단한 문제다.
알고리즘 분류를 확인해봤을 때, 오일러 피 함수라는 생소한 분류가 보인다.
그렇다면 오일러 피 함수란 대체 뭘까?

오일러 피 함수

나무위키에 오일러 피 함수를 검색해본다면 다음과 같은 수식을 확인할 수 있다.

이 때, $\varphi(n)$ 은 n보다 작으며, n과 서로소 관계에 있는 자연수의 개수를 의미한다.

오일러 피 함수는 아래와 같은 특징을 가진다.

1. 소수의 경우

p가 소수일 때, $\varphi(p) = p-1$ 이 성립한다. p가 소수라면 1~p-1 까지의 모든 자연수와 서로소이기 때문.

2. 소수 거듭제곱의 경우

p가 소수이며, k가 자연수일 때 아래 수식이 성립한다.

\varphi(p^k) = p^k - p^{k-1} = p^k(1-\frac{1}{p})

예시는 아래와 같다.

$\varphi(2^3) = \varphi(8) = 8-4 = 4$

3. 곱셈적 성질

서로소인 m, n에 대해서 $\varphi(mn) = \varphi(m)\times\varphi(n)$ 이 성립한다.
서로소가 아닌 두 자연수에 대해서는 성립하지 않는다. 즉, 완전 곱셈적 성질을 갖지는 않는다.

4. 일반 공식

$n=p_1^{a_1}p_2^{a_2}p_3^{a_3}p_4^{a_4}...$ 으로 소인수분해할 수 있을 때, 아래 공식이 성립한다.

\varphi(n) = n \prod_{i=1}^{k}\left(1 - \frac{1}{p_i}\right)

예시는 아래와 같다.

$\varphi(12) = 12(1-\frac{1}{2})(1-\frac{1}{3}) = 4$

이 일반 공식을 사용한다면 쉽게 풀어낼 수 있다.

소스코드

import java.io.*;

public class Main {
    static long N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Long.parseLong(br.readLine());

        long res = N;
        for (long i = 2; i <= Math.sqrt(N); i++) {
            if (N % i == 0) {
                res -= res / i;
                while (N % i == 0) N /= i;
            }
        }

        if (N > 1) res -= res / N;
        System.out.println(res);
    }
}