[백준 19577] 수학은 재밌어

오일러 피함수 문제

www.acmicpc.net/problem/19577

 

www.acmicpc.net/problem/11689

오일러 피함수를 모른다면 위 문제를 먼저 푸는 것을 권장합니다.

---

[문제 풀이]

 

n이 주어졌을 때 xφ(x) = n를 만족하는 가장 작은 x를 출력해야 합니다.

n보다 작은 x(1 <= x < n)를 탐색하면서 xφ(x) = n를 만족하는지 확인하면 답은 구할 수 있습니다.

 

그러나 오일러 피함수를 구하는 시간복잡도가 O(sqrt(n))인데 n만큼 반복한다면 시간복잡도는 O(n sqrt(n))이 되고, n의 최댓값이 10^9까지 가능하므로 O(n sqrt(n))으로는 무조건 시간초과가 발생합니다.

 

오일러 피함수에서 시간복잡도를 줄일 수는 없으므로 불필요한 탐색과정을 없앤다면 시간복잡도를 줄일 수 있습니다.

문제 조건인 xφ(x) = n를 보면 굳이 n보다 작은 모든 수에 대해 반복할 필요는 없어 보입니다.

 

x는 정수고, φ(x)도 정수고, n도 정수라는 점을 인지하고 식을 φ(x) = n/x로 변형해서 생각해봅시다.

n/x가 실수라면 φ(x)가 무슨 값이어도 φ(x) = n/x는 모든 x에 대해 거짓이 되므로, n이 x로 나눠지지 않는다면 φ(x)를 찾아볼 필요가 없습니다.

즉, n/x가 정수인 모든 x에 대해서만 φ(x)를 구하고 xφ(x) = n인지를 확인하면 향상된 성능으로 답을 구할 수 있습니다.

 

바꿔 말해서 이제 이 문제는 n의 약수인 x에 대해 φ(x)를 구하는 문제로 바뀌게 됩니다.

 

O(sqrt(n))의 복잡도로 약수를 구하고, O(sqrt(n))의 복잡도로 오일러 피함수를 구하고, n의 약수인 x에 대해서만 φ(x)를 구한다면 무난하게 통과할 수 있습니다.

 

이미 충분하지만 성능을 더 향상시키고 싶다면, 1을 제외한 모든 홀수에 대해서 -1을 출력하게 하면 됩니다.

xφ(x)라는 식의 특성상, 홀수가 존재할 수가 없습니다.

x가 짝수라면 xφ(x)는 무조건 짝수이고, x가 홀수라면 φ(x)가 짝수가 되므로 xφ(x)는 무조건 짝수입니다.

 

---

[소스 코드] / Python 3

 

def Euler(cur):
    e = cur
    for i in range(2, int(cur**(1/2) + 1)):
        if cur % i == 0:
            e //= i; e *= i - 1
            while cur % i == 0:
                cur //= i
    
    if cur > 1: e //= cur; e *= cur - 1
    return e

N = int(input())

if N == 1 or N == 2: print(N)
elif N % 2 == 1: print(-1)
else:
    arr = [1, 2]
    for i in range(3, int(N**(1/2)) + 1):
        if (N % i == 0): arr.append(i)

    for i in range(len(arr) - 1, -1, -1):
        if (N // arr[i] != arr[i]): arr.append(N // arr[i])
    
    result = -1
    for i in range(2, len(arr)):
        if Euler(arr[i]) * arr[i] == N: 
            result = arr[i]
            break

    print(result)