백준 11778번: 피보나치 수와 최대공약수 [C++]

작성일 | In
플래티넘 V 플래티넘 V

문제

피보나치 수와 최대공약수

풀이

피보나치 수의 최대공약수는 아래를 이용해 구할 수 있습니다.

\[\gcd(F_n, F_m) = F_{\gcd(n, m)}\]

행렬을 사용한 선형 점화식 계산과 분할 정복을 이용한 거듭제곱을 이용하거나 점화식을 변형하여 분할 정복으로 $F_{\gcd(n, m)}$을 로그 시간에 구할 수 있습니다.

해당 명제를 증명하기 전에 알아야 할 몇 가지 정리들을 먼저 알아봅시다.

유클리드 호제법

\[a \equiv r \pmod b \Rightarrow \gcd(a, b) = \gcd(b, r)\]

여기서 증명은 생략합니다.

보조정리 1

\[F_n = F_{k + 1}F_{n - k} + F_kF_{n - k - 1}\]

$k = 0$일때 자명하게 성립합니다.

$k = m$일때 성립한다고 가정합시다.

\[\begin{align} F_n &= F_{m + 1}F_{n - m} + F_mF_{n - m - 1} \\ &= F_{m + 1}(F_{n - m - 1} + F_{n - m - 2}) + F_mF_{n - m - 1} \\ &= F_{m + 2}F_{n - m - 1} + F_{m + 1}F_{n - m - 2} \end{align}\]

따라서 $k = m + 1$일때도 성립함을 알 수 있습니다. 따라서 모든 음이 아닌 정수 $k$에 대해 성립합니다.

보조정리 2

\[\gcd(F_n, F_{n - 1}) = 1\]

$F_n \equiv F_{n - 2} \pmod{F_{n - 1}}$이므로 유클리드 호제법에 의해서 $\gcd(F_n, F_{n - 1}) = \gcd(F_{n - 1}, F_{n - 2}) = \gcd(F_{n - 2}, F_{n - 3}) = \dots = \gcd(F_1, F_0) = 1$

보조정리 3

\[\gcd(a, b) = 1 \Rightarrow \gcd(a, bc) = \gcd(a, c)\]

자명한 성질이므로 증명은 생략합니다.

증명

일반성을 잃지 않고 $n \ge m$이라 합시다.

보조정리 1에서 $k = m - 1$을 대입하면 $F_n = F_mF_{n - m + 1} + F_{m - 1}F_{n - m}$ 입니다. 따라서 $F_n \equiv F_{m - 1}F_{n - m} \pmod{F_{m}}$입니다.

$F_{n - m}$에 대해서도 보조정리 1에서 $k = m - 1$을 대입하면 $F_n \equiv F_{m - 1}^2F_{n - 2m} \pmod{F_{m}}$임을 알 수 있습니다.

따라서 $n = mq + r$로 두면 $F_n \equiv F_{m - 1}^qF_r \pmod{F_{m}}$입니다. 유클리드 호제법을 쓰면 $\gcd(F_n, F_m) = \gcd(F_m, F_{m - 1}^qF_r)$입니다.

이때 보조정리 2와 3에 의해서 $\gcd(F_m, F_{m - 1}^qF_r) = \gcd(F_m, F_r)$입니다. 따라서 $\gcd(F_n, F_m) = \gcd(F_m, F_r)$이고 $\gcd(F_n, F_0) = F_n$이므로 유클리드 호제법 $\gcd(n, m) = \gcd(m, r)$에 의해서 $\gcd(F_n, F_m) = F_{\gcd(n, m)}$입니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr ll MOD = 1e9 + 7;

vector<vector<ll>> operator*(
    const vector<vector<ll>>& v1,
    const vector<vector<ll>>& v2
) {
    vector<vector<ll>> ret(v1.size(), vector<ll>(v2[0].size()));

    for (int i = 0; i < (int)v1.size(); i++) {
        for (int j = 0; j < (int)v2[0].size(); j++) {
            for (int k = 0; k < (int)v2.size(); k++) {
                ret[i][j] += v1[i][k] * v2[k][j];
                ret[i][j] %= MOD;
            }
        }
    }

    return ret;
}

vector<vector<ll>> mat = {
    {1},
    {0},
},
base = {
    {1, 1},
    {1, 0},
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n, m;
    cin >> n >> m;

    while (m) {
        n %= m;
        swap(n, m);
    }
    n--;

    while (n) {
        if (n & 1)
            mat = base * mat;
        base = base * base;
        n >>= 1;
    }

    cout << mat[0][0];

    return 0;
}

백준 11778번: 피보나치 수와 최대공약수 [C++]