[JAVA][Baekjoon] 11689번 GCD(n, k) = 1 🌟🌟🌟🌟

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

 

---

📌 접근 방식

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 1 ≤ k ≤ n의 개수를 구하는 문제이다.
➡️ 즉, n과 서로소(공약수가 1뿐인 수) 인 숫자의 개수를 찾아야 한다.

이를 해결하기 위해 오일러 피 함수를 사용했다.

[알고리즘] 정수론 : 오일러의 피

간단히 말해서 P[i] = P[i] - P[i] / n(소수) 이런 공식이다!

소인수에 해당하는 배수를 제거하는 방식으로 개수를 계산한다.

 

이 문제를 단순하게 해결하려면 1부터 n까지 GCD(n, k)를 모두 계산해야 한다.
하지만 n의 값이 최대 10^12까지 가능하므로 O(n) 시간 복잡도로는 비효율적이다.

이를 해결하기 위해 오일러 피 함수(φ(n))를 사용하면 O(√n)의 시간 복잡도로 최적화할 수 있다.

---

✅ PASS CODE

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        System.out.println(GCD(n));
    }
    public static long GCD(long n) {
        long result = n;
        for(long i=2; i<=Math.sqrt(n); i++) {
            if(n%i == 0) {
               result = result - result/i;
               while(n%i == 0) {
                   n = n/i;
               }
            }
        }
        if(n>1) {
            result = result - result/n;
        }
        return result;
    }
}

 

1️⃣ 2부터 √n까지 반복

• 2부터 √n까지 반복하면서 n을 나눌 수 있는 소인수를 찾는다.
• 왜 √n까지만 확인할까?
  • 소인수는 항상 짝을 이루는데, 하나의 소인수가 √n보다 크면 그 짝은 √n보다 작기 때문!
  • 예를 들어 n = 45이면 
    
    1. √45 ≈ 6.7 → 2부터 6까지 확인하면 된다.
    2. 2는 45를 나눌 수 없다.
    3. 3은 45를 나눌 수 있다! → 3 × 15 = 45
    4. 5는 15를 나눌 수 있다! → 5 × 3 = 15
    5. 즉, 45의 소인수는 3과 5이다.
    6. 이때 (3, 15), (5, 9)처럼 항상 짝을 이루는 것을 볼 수 있다.
    7. 👉 결론: 소인수를 구할 때 √n까지만 확인하면 모든 소인수를 찾을 수 있다! 🚀

2️⃣ 소인수 찾기

• 현재 i가 n을 나누어떨어지게 만들면 i는 n의 소인수이다.
• 즉, n % i == 0이면 i는 n의 소인수임을 알 수 있다.
• 예를 들어, n = 45라면 
  1. i = 2 → 45 % 2 != 0 → 2는 소인수가 아니다.
  2. i = 3 → 45 % 3 == 0 → 3은 소인수이다!
  3. i = 4 → 45 % 4 != 0 → 4는 소인수가 아니다.
  4. i = 5 → 45 % 5 == 0 → 5는 소인수이다!
  5. 즉, n = 45의 소인수는 3과 5이다. 🎯
  6. 💡 핵심: i가 n을 나누어떨어지면 그 i는 반드시 n의 소인수이다! 🚀

3️⃣ n에서 i의 배수를 제거

• n의 소인수가 i라면, i의 배수들은 n과 공약수를 가지므로 제거해야 한다.
• 오일러 피 함수의 원리에 따라 result -= result / i 를 수행한다.
  • 즉, n에서 i의 배수를 제외한 개수를 남기는 과정이다.
• 예를 들어, n = 45일때, 45의 소인수는 3과 5이다.
  1. 3의 배수 제거: result = 45 - (45 / 3) = 45 - 15 = 30
  2. 5의 배수 제거: result = 30 - (30 / 5) = 30 - 6 = 24
  3. 결과 :  45 이하의 수 중에서 45와 서로소인 숫자의 개수는 24개이다! 🎯
  4. 💡 핵심: 소인수 i가 발견될 때마다 result -= result / i를 수행하면, n과 서로소인 숫자의 개수를 구할 수 있다! 🚀

4️⃣ 같은 소인수 제거

• n이 i로 나누어떨어진다면, n에서 해당 소인수를 계속 나눠서 제거해야 한다.
• 즉, n이 i로 나누어지는 동안 계속 나누어주면,
  • 같은 소인수가 여러 번 나오는 경우를 방지할 수 있다.
• 예를 들어, n = 45라면, 45의 소인수는 3과 5이다.
  • 3으로 나누기 : 45 ÷ 3 = 15 15 ÷ 3 = 5 (3으로 더 이상 안 나눠짐) → 3을 모두 제거한 후, n = 5가 됨
  • 5로 나누기 : 5 ÷ 5 = 1 → 5를 모두 제거한 후, n = 1이 됨
  • 결과 :  소인수 i를 찾은 후, n이 i로 나누어질 때까지 계속 나누어주면 중복 제거가 가능하다! 🎯
  • 💡 핵심: 같은 소인수가 여러 번 등장하는 것을 방지하기 위해, n을 i로 계속 나눠 완전히 제거해야 한다! 🚀

5️⃣ 마지막 소수 처리

• 예를 들어, n = 45라면, 45의 소인수는 3과 5이다.
  • 45를 3으로 계속 나누어주면 5가 남음
  • 5의 제곱근은 현재 위치인 4보다 작기 때문에 반복문을 나오게됨
  • n>1에 포함되기 때문에 5를 마저 처리해줘야함! 
  • 💡 핵심: 반복문이 끝난 후에도 n > 1이면, 남은 n이 소수이므로 한 번 더 제거해야 한다! 🚀

---

😊 느낀 점

오일러 피 함수는 소인수의 배수를 제거하는 과정을 이해하면 직관적으로 접근할 수 있었다.
처음에는 1부터 n까지 모든 수와 GCD를 계산하려고 했지만, O(n)의 시간 복잡도로 비효율적이었다.
그러나 제곱근(√n)을 활용하면 O(√n)으로 최적화할 수 있다는 점을 깨달았다.

또한, 제곱근까지만 탐색하면 마지막 소수가 남을 수 있기 때문에 n > 1 체크를 빼먹지 않는 것이 중요하다는 것도 잊지 말기!