Boj 10327) 피보나치 문제해결전략

문제

백준 10327

설명

Gabonachi 를 주어진 시작 수 a, b 로 구성해보면

• a, b, a+b, a + 2b, 2a+3b, 3a + 5b, 5a + 8b, 8a + 13b, ...
• a, b 의 계수가 피보나치 수임을 알 수 있음.
• 다시말해 \(F_{n-1} \times a + F_{n} \times b = C\)

가장 작은 a, b 를 구해야하므로 피보나치의 계수가 큰 경우부터 계산하면 됨.

• 주어진 숫자보다 바로 작은 두 피보나치 수부터
• \(F_{n-1} \times a + F_{n} \times b = C\) 를 만족하면서
• \(0 < a < b\) 인 수가 존재하는지 찾고
• 없는 경우 그것보다 작은 피보나치로 교체 후 반복하면 됨.

이를 구하는 방법은 2가지가 있음.

• 피보나치가 기하급수적으로 커지므로 주어진 인풋으로는 브루트포스 도 가능함
• 혹은 확장 유클리드 호제법 을 이용해 빠르게 구할 수 있음.

시간 복잡도

O(N) or O(LogN)

코드

/ *
 * a, b, a+b, a + 2b, 2a+3b, 3a + 5b, 5a + 8b, 8a + 13b, ... p1*a + p2*b
 * get minimal a, b from given p1 and p2
 */

pair<int, int> BruthForce(int input, int p1, int p2)
{
    for (int b = 1; b * p2 < input; b++)
    {
        int tmp = input - p2 * b;
        int a = tmp / p1;
        if (tmp % p1 == 0 && a <= b)
            return { a, b };
    }
    return { -1, -1 };
}

// s0 * a + t0 * b = r1 => multiply input / r1
pair<int, int> EEA(int64_t input, int p1, int p2)
{
    int r0 = p2, r1 = p1, s0 = 1, s1 = 0, t0 = 0, t1 = 1;
    int tmp = 0, q = 0;

    while (r1) {
        q = r0 / r1;
        tmp = r0;
        r0 = r1; r1 = tmp - r1 * q;
        tmp = s0;
        s0 = s1; s1 = tmp - s1 * q;
        tmp = t0;
        t0 = t1; t1 = tmp - t1 * q;
    }
    
    pair<int64_t, int64_t> ans = { t0 * input , s0 * input };
    int64_t offset = p1 + p2;
    int64_t mul = (ans.second - ans.first) / offset;
    
    ans.first += p2 * mul;
    ans.second -= p1 * mul;
    if (ans.first > ans.second)
    {
        ans.first -= p2;
        ans.second += p1;
    }
    
    if (ans.first <= 0 || ans.second <= 0 || ans.first > ans.second)
        return { -1, -1 };
    
    return ans;
}

int pivos[51];

int main()
{
    pivos[0] = 1; pivos[1] = 1;
    for (int i = 2; i < 51; i++)
        pivos[i] = pivos[i - 1] + pivos[i - 2];
    
    int n = 1;
    cin >> n;
    
    while (n--)
    {
        int input, i = 0;
        cin >> input;
    
        while (pivos[i++] < input);
        while (i-- >= 2)  // max ~50
        {
            auto c = EEA(input, pivos[i - 2], pivos[i - 1]); // Bruthforce
            if (c.first != -1)
            {
                cout << c.first << ' ' << c.second << endl;
                break;
            }
        }
    }
}