[백준] 11689 GCD(n,k) = 1 java 풀이

1. 문제 설명 📌

(1) 링크🔗

https://www.acmicpc.net/problem/11689

(2) 해설🕵

오일러의 피를 알고 있는지 묻는 문제이다. 오일러의 피 함수 $φ(n)$ 이란, n 이하 자연수 중 n과 서로소인 숫자의 개수를 반환하는 함수이다.
저번 오일러의 피 이론 정리 포스팅에서는 N개의 영역 내의 모든 수에 대한 오일러의 피 함수를 구했는데, 이번 문제는 N의 최대값이 $10^{12}$ 여서 그러한 배열을 만들 수도 없고, 문제에서도 N 하나에 대한 오일러 피 함수를 구하라 했으므로, N에 대해서만 오일러 피 함수를 구하면 된다.

2. 생각의 흐름: 코드가 나오기까지 🗃️

(1) IDEA 도출💡

KEY WORD: 에라토스테네스의 체, 오일러 피 함수

에라토스테네스의 체를 따로 구할 메모리나 시간이 없다. 따라서 그냥 i = 2부터 시작해서 $ \sqrt{N}$까지 모든 수를 확인한다. 이러면 $10^{6}$까지만 확인하면 되어서 시간 초과는 나지 않는다. 해당 문제는 말로만 설명하기 어려워 SUDO CODE를 먼저 확인하고, 부연 설명을 이어가겠다.

(2) SUDO CODE 📜

• 0️⃣ ans: 오일러 피 함수의 결과, n: 오일러 피 함수의 인수(입력), p = 만나는 소수
• 1️⃣ p = 2부터 $\sqrt{n}$ 까지 확인한다.
• 2️⃣ 만약 n%p == 0이면 p는 n의 소인수이다! (p는 $\sqrt{n}$내의 모든 수인데, 왜 그렇게 되는지는 뒤에 가서 설명하겠다.)
• 3️⃣ n이 p로 나누어 떨어지지 않을 때까지 p로 나눈다.
• 4️⃣ 이후 ans = ans - ans/p 계산을 한다. (오일러의 곱 공식을 점진적으로 적용)
• 5️⃣ 1~4의 반복이 끝났는데도, n > 1이면, ans = ans - ans/n을 해준다.
• 6️⃣ 답은 ans임

(3) 부가 설명

2️⃣번에서 n%p == 0이 되는 p는 무조건 소수인 이유

3️⃣번에서 해당 소수의 제곱을 모두 제거했다. 예를 들어 $2^{11} * 7$이라는 숫자이면 2를 만났을 때, $2^{11}$을 모두 없애는 것이다. 즉 이후 2의 배수들은 n을 절대 나누어 떨어지게 나누지 못한다. 이렇게 계산을 이어갔는데도 임의의 수 k가 n%k == 0에 성공했다면 k는 n의 소인수인 것이다.

1️⃣번을 $\sqrt{n}$ 까지만 반복하는 이유와 5️⃣번

$\sqrt{n}$이하의 소수까지만 오일러의 곱 공식 연산을 하는 이유는 무엇일까? 그 이유는 $\sqrt{n}$보다 큰 소수는 n 이하에서 최대 한개만 존재하기 때문이다. 귀류법으로 증명하면,
예를 들어 $ \sqrt{n}$보다 큰 소인수가 $p_1$, $p_2$ 두 개 존재한다고 치자. 근데 이래버리면 $p_1 * p_2$ 가 $ \sqrt{n} * \sqrt{n}$ 보다 클 것이고, 이러면 이미 두 수는 N의 소인수(N을 구성하는 소수)라는 정의에 어긋나게 된다.

따라서 $\sqrt{n}$까지의 소수만 구하고, n이 아직도 1보다 큰지 확인해서, 크면 $\sqrt{n}$보다 큰 소수가 하나 존재하니 그에 대한 계산을 해주면 되는 것이다.

(4) 시간복잡도 분석 🕓

이 방식의 구현은 에라토스테네스의 체 구현의 변형으로 에라토스테네스의 체와 시간복잡도가 아주 유사하다. 고로

$O(N log(log N))$

3. 구현 코드 🔎

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


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());
        System.out.println(euler_phi_f(N));
    }

    public static long euler_phi_f(long n){
        if(n == 1) return 1;
        long ans = n;
        for(long p = 2; p <= Math.sqrt(n); p++){
            if(n%p == 0) ans = ans - (ans/p);
            while (n%p == 0) n /= p;
        }
        if(n > 1) {    // n의 제곱근보다 큰 소수는 최대 하나만 존재한다.
            ans = ans - ans/n;
        }
        return ans;
    }
}

4. 배운 것들 🎯

오일러의 피 함수를 다른 방식으로 구현하는 방법에 대해서 배웠다.