백준 26036번 문제 링크
문제 이름 : 제곱 ㄱㄱ
주 언어 : Python
태그 : 수학 / 정수론 / 구성적
solved.ac 등급 : Platinum I (2023/02/11 확인)
문제 보기
문제 :
BOJ의 쉬운 문제 제곱 ㄴㄴ 를 풀지 못해 화가 난 명준은 제곱ㄴㄴ수를 뒤집은 제곱ㄱㄱ수를 만들어냈다.
양의 정수 X의 모든 소인수 p에 대하여 p2도 X의 약수라면, X를 제곱ㄱㄱ수라고 한다. 첫 제곱ㄱㄱ수는 1, 4, 8, 9, 16, 25, 27, 32, ... 이다.
제곱ㄱㄱ수를 하나 찾아내는 것은 쉽다. 아무 거듭제곱수를 잡으면 곧 제곱ㄱㄱ수이기 때문이다. 또 명준은 모든 제곱ㄱㄱ수는 제곱수와 세제곱수를 곱한 형태로 표현할 수 있다는 것도 알아냈다.
원하는 크기의 제곱ㄱㄱ수 하나를 찾는 것이 쉽기 때문에, 명준은 이웃한 두 양의 정수가 모두 제곱ㄱㄱ수가 되는 경우를 찾으려고 한다. 명준이 원하는 크기의 이웃한 두 제곱ㄱㄱ수가 있는지 찾아주자!
입력 :
첫째 줄에 정수 N이 주어진다. (0 ≤ N < 1000)
출력 :
$A$와 $A + 1$ 가 모두 제곱ㄱㄱ수이고, $100^{N} ≤ A < 100^{N+1}$ 을 만족하는 $A$를 찾으면 된다.
조건을 만족하는 $A$가 존재하는 경우, 첫째 줄에 $A = B^{2}C^{3}$ 인 두 양의 정수 $B$, $C$를 출력한다.
이어서 둘째 줄에 $A + 1 = D^{2}E^{3}$ 인 두 양의 정수 $D$, $E$를 출력한다.
조건을 만족하는 $A$가 여럿 있다면 그 중 하나에 대한 답만을 출력한다.
조건을 만족하는 $A$가 없는 경우에는 첫째 줄에 -1을 출력하고 종료한다.
제곱 ㄱㄱ 수는 수학적으로 강력수 와 동일합니다.
$n$이 제곱 ㄱㄱ 수(강력수) 인것은 $n = a^2 b^3$인 정수 $a$, $b$가 있는 것과 동일하므로 펠 방정식 $x^{2} - 8 y^{2} = 1$의 정수해를 찾아주면 됩니다. ($8 = 2^3$)
이때, 펠 방정식 풀이법에 따라 초기해를 $x_{1} = 3$, $y_{1} = 1$로 잡고, 점화식 $x_{k+1} = x_1 x_k + n y_1 y_k$, $y_{k+1} = x_1 y_k + y_1 x_k$ 에 따라서 해를 찾아줍니다.
260번째 푼 문제 (2022/11/21)
+ 23/01/15) 분명히 처음 풀 때는 플레III 였는데 지금 확인해보니 플레I 문제가 되었습니다.