[백준 10327] 피보나치 문제 해결 전략

확장된 유클리드 알고리즘을 사용하는 문제이다. 처음 배워 보는 알고리즘으로 풀어보는 거라 신박했다.

1. 초항 구하기

먼저 \(a,b\)가 자연수라는 조건을 무시하고 진행해보자. 알아낼 수 있는 사실로는 아래의 식을 구해볼 수 있다.
$$F_k=ax+by$$
왜냐하면 피보나치수열의 초항이 더해지는 형태이기 때문에 이런식이 나올 수 있다. 또한 여기서 \(x, y\)가 무엇인지도 알 수 있다.
$$F_k=F_{k−2}a+F_{k−1}b$$
이 식이 나오는 이유는 직접구해보면 알 수 있을 것이다. 이런 형태면 확장 유클리드 호제법을 사용할 수 있는 형태가 된다. \(k\)는 범위가 작으니 모두 해봐도 된다.

가능한 \(a,b\) 중 제일 작고 자연수인 것이 초항이 될 것이다. 하지만 확장 유클리드 호제법은 정수인 \(a,b\)를 구하기 때문에 자연수 \(a,b\)를 구하기 위해서는 다른 방법이 필요하다.

2. 자연수인 초항 구하기

위의 식의 선형 디오판토스 방정식 꼴을 가지며 \(a,b\)가 유일한 해가 아니다. 그러므로 다른 해를 구할 수 있다면 그 해 중 자연수 \(a,b\)만 고르면 되지 않을까? 라는 생각을 할 수 있다.

선형 디오판토스 방정식의 다른 해는 아래의 공식을 대입해서 구할 수 있다.
$$a_2 = a_1 + k\frac{y}{gcd(x, y)}$$
$$b_2 = b_1 - k\frac{x}{gcd(x,y)}$$
여기서 알 수 있는 사실은 \(x = F_{k-2}, y = F_{k-1}\) 이고, \(gcd(F_{k-2}, F_{k-1}) = 1\) 이라는 사실을 알 수 있다. 그리고 자연수일 조건 부등식을 적용하면 \(k\)값을 손 쉽게 알아낼 수 있다.
$$0 < a_1 + ky, \frac{-a_1}{y} < k$$
$$0 < b_1 - kx, \frac{b_1}{x} > k$$
$$k= min([\frac{-a_1}{y}], [\frac{b_1}{x}])$$
우리는 \(a,b\)가 자연수가 되는 \(k\)를 찾았으므로 대입해주기만 하면 바로 자연수인 초항을 바로 구할 수 있다.

3.소스 코드

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pll;
 
pll exeuc(ll a, ll b, ll w) {
    if (b == 0)
        return { 1, 0 };
    pll p = exeuc(b, a % b, w);
    return { p.second, p.first - (a / b) * p.second };
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    vector<ll> pibo;
    pibo.push_back(1);
    pibo.push_back(1);
    while (true) {
        int sz = pibo.size();
        if (pibo[sz - 1] + pibo[sz - 2] > 1e9) break;
        pibo.push_back(pibo[sz - 1] + pibo[sz - 2]);
    }
 
    int tc; cin >> tc;
 
    while (tc--) {
        ll n; cin >> n;
 
        pll ans = { 1e9, 1e9 };
        for (int i = 0; i < pibo.size() - 2; i++) {
            ll a = pibo[i], b = pibo[i+1];
 
            pll p = exeuc(a, b, n);
            p.first*=n, p.second*=n;
 
            ll x = p.first, y = p.second;
 
            ll k = min(ceil((double)y / a), ceil((double)-x / b));
 
            x = x + b * k;
            y = y - a * k;
 
            if (x < 0 || y < 0) continue;
 
            if (x + y < ans.first + ans.second)
                ans = { x, y };
        }
 
        if (ans.first > ans.second || ans.first == 0)
            cout << ans.second << " " << ans.first + ans.second << "\n";
        else
            cout << ans.first << " " << ans.second << "\n";
    }
    return 0;
}