수학은 재밌어

• 그냥 쉽게 떠오르는 방법은, 가능한 모든 x에 대해서 일일히 φ(x)를 계산해서 xφ(x)=n 이 되는 x를 찾는 것이다. 가능한 x의 후보는 n의 모든 약수들이다.
• 쉽게 떠오르지만, 시간 안에 돌아갈지 확신이 잘 안섰다. 모든 약수에 대해서 오일러 피 함수를 계산한다면.. 오일러 피 계산이 O(n^1/2)이고.. 약수의 갯수도 O(n^1/2)인건가..? 그러면 곱해서 O(n)이면 빡세지 않나하고 생각하고 다른 방법으로 구하는 방법을 막 고민했다..
  • x=ab이면 xφ(x)=aφ(a)*bφ(b)니까.. x가 p1^e1*p2^e2*… 으로 소인수분해된다면, xφ(x)를 p1^(e1*2-1)*(p1-1) * p2^(e2*2-1)*(p2-1).. 이런 형태가 되니까.. 그러면 이게 n이 되는 걸 찾으려면 n을 먼저 소인수분해하고.. 하는 쓸데없는 풀이를 생각하고 있었다..
• 그러다가 10^9 이하 범위에서 약수를 가장 많이 갖는 수도 약수가 1000개 정도밖에 안된다는 사실을 알게 되었다. (그래서 PS범위에서는 대략 O(n^1/3)으로 처리한다는 것도 알게 되었다). 어 그럼 그냥 처음 생각한 무식한 방법을 그냥 써도 되겠는데?
• 그래서 그냥 처음 생각한 방식으로 돌렸더니 44ms만에 광속으로 풀렸다..;; 이게 느리게 돌 경우에 대비해서 소인수분해를 빨리 하기 위해서 미리 소수 목록을 뽑아놓은 다음에 시도하는 것도 생각하고 있었는데 그럴 필요가 전혀 없었다.
• 사실 소인수분해가 O(n^1/2)까지 걸릴려면 n이 소수여야 할거고, 인자가 많아질수록 시간이 줄어들텐데.. 약수중에서 소수인거는 별로 없을테니까.. 암튼 그래서 실제 시간복잡도는 계산한 값 O(n^1/2 * n^1/3) 보다도 훨씬 작아질것 같다..

"""Solution code for "BOJ 19577. 수학은 재밌어".

- Problem link: https://www.acmicpc.net/problem/19577
- Solution link: http://www.teferi.net/ps/problems/boj/19577

Tags: [Number theory]
"""

import math
from teflib import numtheory


def euler_phi(n):
    for p in numtheory.prime_factorization_small(n):
        n -= n // p
    return n


def main():
    n = int(input())
    for i in range(1, math.isqrt(n) + 1):
        if n % i == 0 and euler_phi(n // i) == i:
            print(n // i)
            break
    else:
        print('-1')


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.prime_factorization_small