링크

문제 요약

$G_i=G_{i-1}+G_{i-2}, (i>2)$ 라는 점화식의 초항 2개, $G_1$ 과 $G_2$ 를 적절히 설정하여, 자연수 $N$ 이 나타나도록 만드려고 한다. 이때 최소한의 초항 쌍을 찾아라. 최소한의 초항 쌍이란, $G_2$ 가 작은 것이 우선순위이며, 만약 해당 값이 같다면 $G_1$ 값이 더 작은 경우가 최소한의 초항 쌍이다.

관찰

위의 점화식을 그대로 대입을 해서 관찰을 시작하자. 그러면 아래와 같은 규칙을 발견할 수 있다.

\[G_1\times{1}+G_2\times{0}=G_1\] \[G_1\times{0}+G_2\times{1}=G_2\] \[G_1\times{1}+G_2\times{1}=G_3\] \[G_1\times{1}+G_2\times{2}=G_4\] \[G_1\times{2}+G_2\times{3}=G_5\] \[\vdots{}\] \[G_1\times{ F_{i-2} }+G_2\times{ F_{i-1} }=G_i\]

이때 $F_i$ 는 피보나치 수열의 $i$ 번째 값이다. 위의 규칙으로부터 우리는 본 문제를 부정 방정식의 해를 구하는 문제로 해석할 수 있다는 것을 알 수 있다.

풀이

그렇다면 부정 방정식을 총 몇개나 풀어야 할까? 알다시피 피보나치 수열의 값은 exponential 하게 증가하므로 대략 $O(\log{N})$ 개의 상한선을 가짐을 추측할 수 있다. 따라서 각 부정 방정식을 확장 유클리드 알고리즘을 이용하여 계산하면, 1개의 테스트 케이스에 대하여 $O(\log^2{N})$ 의 시간이 걸리게 된다.

참고로 해가 존재하는 여러 경우의 수 중에 $G_2$ 값이 최소가 될 수 있도록, 확장 유클리드 알고리즘을 통해 얻은 특이해를 조정하는 과정이 필요할 것이다. 또한 그러한 쌍중에 문제에서 제시한 바의 정의에 입각하여 최솟값을 구하면 문제는 풀리므로, 총 $O(T\log^2{N})$ 의 시간에 문제가 해결된다.