백준 19577번: 수학은 재밌어 (Java, 오일러피, 정수론)

HamJina·2025년 7월 24일

19577번 백준19577번 백준수학은재밌어 백준오일러피 수학은재밌어

백준

목록 보기

2/17

☑️ 문제

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

✔️관련 알고리즘 개념 - 오일러피 함수

오일러피

☑️ 문제 분석

어떤 양의 정수 n이 있다고 할 때, xφ(x) = n을 만족하는 양의 정수 x가 존재하는가?

양의 정수 x가 존재하면 ⇒ 최소의 x를, 존재하지 않으면 ⇒ −1을 출력한다.

위 조건을 만족하도록 알고리즘을 구성해야 한다.

⇒ 여기서 x값은 n보다 작거나 같은 양의 정수에서 찾으면 된다.

⇒ 만약 x가 n보다 큰 양의 정수라면 x∅[x] > n이 될 것이기 때문에 문제의 조건을 만족할 수가 없기 때문이다.

예시 입력 1과 같이 n = 2라고 주어진다면

x∅[x] = n을 만족하는 최소 x값은 2이다.

2 x ∅[2] = 2 * 1 = 2값으로 2와 같으므로 양의 정수 x가 존재하고 그 최소값이 2이므로 2를 출력한다.
예시 입력 2와 같이 n = 3이라고 주어진다면
x∅[x] = n을 만족하는 양의 정수 x가 존재하는지 확인해야 한다.
- x = 2일 때, 2 * ∅[2] ≠ 3
- x = 3일 때, 3 * ∅[3] ≠ 3 이므로 양의 정수 x가 존재하지 않으므로 -1을 출력한다.
예시 입력 3과 같이 n = 20이라고 주어진다면
- x를 2부터 반복했을 때, x = 2, 3, 4일 때는 조건을 만족하지 않는다.
- x = 5일 때, 5 ∅[5] = 5 4 = 20 == 20이므로 이를 만족하는 최소 양의 정수값은 5이므로 5를 출력하고 반복문을 멈춘다.

위의 예시 입력을 토대로 문제 풀이 순서롤 써보면

n을 입력받은 다음 ∅[n]함수를 정의한다.
1~n까지의 값을 갖는 ∅[n]함수를 정의한다.
∅[n] 배열에서 인덱스를 앞에서 부터 반복하면서 x∅[x] == n를 만족하는 양의 정수 n이 존재하는지 찾는다.

⇒ 이 방법은 메모리 초과가 발생한다.

그래서 문제 풀이를 수정해보았다.

n을 입력받은 다음 n보다 작거나 같은수를 2부터 차례대로 반복하며
문제 조건을 만족하는 x값을 찾는다. (위의 방법과 다른 점은 x에 대한 오일러 피 함수를 따로 정의하여 전체 오일러피 배열을 정의하는 것이 아니라 하나의 x값에 대한 오일러피 값을 그때 그때 계산하는 것이다.)
만족하는 x값을 찾으면 결과 출력

⇒ 하지만 이 방식은 시간초과가 발생한다. 탐색시 불필요한 탐색을 제거하는 방향으로 가야 한다.

⚠️여기가 이 문제 해결의 핵심이다!!!

우리는 문제를 해결하기 위해 n보다 작은 모든 수에 대해 반복할 필요는 없다. x는 정수고, φ(x)도 정수고, n도 정수이다. 식을 φ(x) = n/x로 변형해서 생각해보면, φ(x)가 정수가 나오려면 n/x역시 정수가 나와야 한다. n/x가 정수가 나오려면 x가 n의 약수인 경우밖에 없다. 바꿔 말해서 이제 이 문제는 n의 약수인 x에 대해 φ(x)를 구하는 문제로 바뀌게 됩니다. ⇒ n에 대한 약수 배열을 구한 후 해당 배열을 순회하면서 문제를 푼다.

☑️ 코드

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

public class Main {
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine()); // 자연수

        int result = -1;

        // 약수만 순회하도록 개선
        for (int x : getDivisors(n)) {
            if (x * phi(x) == n) {
                result = x;
                break;
            }
        }

        System.out.println(result);
    }

    // 약수 리스트를 반환하는 함수
    private static ArrayList<Integer> getDivisors(int num) {
        ArrayList<Integer> list = new ArrayList<>(); // num의 약수를 저장하는 배열 초기화
        for (int i = 1; i * i <= num; i++) {
            if (num % i == 0) {
                list.add(i);
                if (i != num / i) list.add(num / i);
            }
        }
        list.sort(Integer::compareTo); // 작은 수부터 탐색하게 정렬
        return list;
    }

    // 오일러 피 함수
    private static int phi(int x) {
        int value = x;
        int temp = x;

        for (int i = 2; i * i <= temp; i++) {
            if (temp % i == 0) {
                value = value - value / i;
                while (temp % i == 0) temp /= i;
            }
        }
        if (temp > 1) {
            value = value - value / temp;
        }
        return value;
    }
}