BOJ 13728 행렬식과 GCD

난이도 : Solved.ac 기준 Platinum 4

 

1. 문제 설명 

 

다음과 같은 형태의 $n \times n$ 행렬

$$ M_{n} = (M_{ij}) = \begin{cases} 1 & i = j \\ 1 & j = i+1 \\ -1 & j = i-1 \end{cases} $$ 즉, 예를 들어 $n = 4$ 인 경우 $$ \begin{pmatrix} 1 & 1 & 0 & 0 \\ -1 & 1 & 1 & 0 \\ 0 & -1 & 1 & 1 \\ 0 & 0 & -1 & 1 \end{pmatrix}$$ 이런 형태가 되게 된다. 이때, 다음 값을 계산하는 문제.

$$\sum_{i = 1}^{n} \gcd(\det M_i, \det M_n)$$

 

2. 풀이

먼저, 위 규칙대로 생성된 $n \times n$ 행렬의 행렬식의 수열을 $d_i$ 라고 하자.

이때, $d_1 = 1, d_2 = 2$ 는 직접 계산해서 찾을 수 있다. 

$d_k$ 를 구하기 위해, 행렬식을 첫 행을 기준으로 직접 계산 (Cofactor Expansion) 하는 과정을 써 보면, 

첫 행에서 0이 아닌 entry는 첫 두 개 뿐이며, 그중 첫 열을 기준으로 전개하면 $d_{k-1}$ 을 얻는다. 

두 번째 열을 기준으로 전개하면, 다음과 같은 행렬의 determinant를 계산할 필요가 있음을 알게 된다. 

$$ \begin{pmatrix} -1 & 1 & 0 \\ 0 & 1 & 1 \\ 0  & 1 & 1 \end{pmatrix}$$

이때, 이 새로운 행렬도 다시 여인수 전개해 보면 첫 열에 대해서는 $- d_{k-2}$ 를 얻고, 두 번째 열에 대해서는 rank가 $k-2$ 보다 작으므로 0이 된다. 따라서, 이를 이용하면 

$$d_k = d_{k-1} + d_{k-2}$$ 를 얻으며, 이 식은 피보나치 수열 형태임을 바로 알 수 있다.

 

또한, 피보나치 수열 $f_i$ 에 대해, $\gcd(f_i, f_j) = f_{\gcd(i, j)}$ 임이 잘 알려져 있다.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define mod 1000000007
int fibo[101010] = {0,1};
int32_t main()
{
    int ans = 0;
    int n; cin >> n;
    for (int i = 2; i<=101000; i++)
        fibo[i] = (fibo[i-1]+fibo[i-2])%mod;
    for (int i = 1; i<=n; i++)
    {
        ans += (fibo[__gcd(i+1,n+1)]);
        ans %= mod;
    }
    cout << ans%mod << '\n';
}