[BOJ] 백준 19577 수학은 재밌어 (JAVA)

오일리의 피함수 + 약수 구하기

📑 문제

백준 19577 수학은 재밌어

---

🌱 아이디어

Xφ(X) = N , X의 범위는 N의 약수이다.

 

풀기 전 가장 크게 고민했던 점은 한 가지이다. X를 어떻게 찾아야 하는가이다.

당연하게도 X는 N이하 일 것이다. 하지만 N이 1,000,000,000 경우 탐색범위가 커서, 시간초과가 날것이다

 

첫 번째 시도는 정수 'X'를 이분탐색으로 찾는 것이다. 물론 X마다 오일러의 피 수가 규칙적이지 않아서, 실패했다.

 

두 번째는 시도는 A * B = N이라면 -> 결국 A, B는 N의 약수이다. 라는 아이디어로 시작했다.

당연하게도 두 수를 곱해서 N 이 되려면 두 수는 N의 약수일 것이다. 

 

약수를 구할 때 제곱근까지만 탐색하여. O(logn)만큼 최적화하고

X의 탐색범위를 N의 약수로 획기적으로 줄이고 오일러의 피함수 알고리즘으로 계산하여

조건에 맞는 가장 작은 약수 를 출력하면 된다!

---

🌱 코드 및 풀이

 

---

🌱 느낀 점

원트 성공했다.

 

오일러의 피함수를 연속으로 3문제를 풀어서 쉽게 접근할 수 있었다. 이 문제는 X의 탐색범위를

어떻게 설정하는지 파악하는 게 핵심인 것 같다. 정수론은 배우면 배울수록 신기한 것 같다...