[BaekJoon] 4355 서로소 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static Reader scanner = new Reader();

    static int n;

    static void input() {
        n = scanner.nextInt();
        if(n == 0) {
            System.out.print(sb);
            System.exit(0);
        }
    }

    static void solution() {
        if(n == 1) {
            sb.append(0).append('\n');
            return;
        }
        sb.append(eulerPhi(n)).append('\n');
    }

    static int eulerPhi(int num) {
        int result = num;
        for(int divisor = 2; divisor * divisor <= num; divisor++) {
            if(num % divisor == 0) {
                while(num % divisor == 0) {
                    num /= divisor;
                }
                result -= result / divisor;
            }
        }

        if(num > 1) {
            result -= result / num;
        }

        return result;
    }

    public static void main(String[] args) {
        while(true) {
            input();
            solution();
        }
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

오일러 피(파이) 함수 $\phi(n)$

1부터 n까지의 수 중에서 n과 서로소인 수의 개수

• 서로소 : 두 수 x, y의 공약수가 1뿐인 두 정수

성질

1. $p^k$에서 p가 소수이고, k가 1 이상의 자연수일 때, $\phi(p) = p - 1$을 만족한다.
   • 역으로, $\phi(p) = p - 1$이면, $p$는 소수이다
2. $x$가 $p$의 배수이면, $p^k$과 $x$가 서로소가 아니다.
   • 이에 따라 $p^k$ 이하의 p의 배수인 수는 $p^{k - 1}$개가 존재한다.
   • 즉, $p^k$ 이하의 p의 배수가 아닌 수는 $p^k - p^{k - 1}$개가 존재하는데, 이는 $\phi(p^k)$와 같다. ($p$가 소수이므로)

     $\phi(p^k) = p^k - p^{k - 1} = (p - 1) \times p^{k - 1}$

3. m과 n이 서로소라면, 다음이 성림된다.

   $\phi(mn) = \phi(m)\phi(n)$

위 성질들을 종합하여 생각해봤을 때, 아래와 같은 식이 성립될 수 있다.

$\phi(n) = \phi(m_1^{e_1}m_2^{e_2}m_3^{e_3}...m_k^{e_k}) \\ = m_1^{e_1 - 1}(m_1 - 1)m_2^{e_2 - 1}(m_2 - 1)m_3^{e_3 - 1}(m_3 - 1)...m_k^{e_k - 1}(m_k - 1) \\ = n(1 - \frac{1}{m_1})(1 - \frac{1}{m_2})(1 - \frac{1}{m_3})...(1 - \frac{1}{m_k}) \\ = n(\frac{m_1 - 1}{m_1})(\frac{m_2 - 1}{m_2})(\frac{m_3 - 1}{m_3})...(\frac{m_k - 1}{m_k})$

위 정리 및 수식을 이용하면 해당 문제 풀이가 가능하다.

static int eulerPhi(int num) {
    int result = num;
    for(int divisor = 2; divisor * divisor <= num; divisor++) {
        if(num % divisor == 0) { // 1
            while(num % divisor == 0) {
                num /= divisor;
            }
            result -= result / divisor; // 2
        }
    }

    if(num > 1) { // 3
        result -= result / num;
    }

    return result;
}

1. 주어진 수($n$)를 가장 작은 소수인 2부터 $\sqrt{n}$까지로 소인수 분해를 진행한다.
2. 위에서 주어진 식에 따라 $\phi(n) = n(\frac{m_1 - 1}{m_1})(\frac{m_2 - 1}{m_2})(\frac{m_3 - 1}{m_3})...(\frac{m_k - 1}{m_k})$가 성립되기 때문에 이에 맞게 계산을 진행해나간다.
3. $\sqrt{n}$까지의 수로 소인수 분해를 진행한 다음에 남아있는 수는 1 또는 어떠한 소수가 될 것이다. 그러므로 만약 남아있는 수가 1보다 크다면 해당 소수에 대해서도 2번 과정을 진행해줘야하기 때문에 2번 과정을 남아있는 수에 대해 진행한다.