%2021. 11. 9. 00:30에 작성된 글입니다%
https://www.acmicpc.net/problem/19577
19577번: 수학은 재밌어
xφ(x) = n을 만족하는 양의 정수 x가 존재하면 최소의 x를, 존재하지 않으면 −1을 출력한다.
www.acmicpc.net
오일러 피 함수라는 걸 여기서 처음 봤다.
대충 위키에서 본 내용에 따르면 이 함수는 아래의 성질을 갖는다고 한다.
\(\gcd \left(a,b\right)=1\)일 때, \(\phi \left(ab\right)=\phi \left(a\right)\phi \left(b\right)\)
\(\phi \left(p^n\right)=p^n\left(1-\frac{1}{p}\right)=p^{n-1}\left(p-1\right)\)
그럼 주어진 \(n\)에 대해서 큰 소수부터 쭉 내려가며 \(p-1\)으로 나누어떨어지는 순간에 \(p^2n-1\) (\(x\phi(x)\)이므로)을 끌고 오면 되는 거 아닐까?