$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

BOJ 13728 행렬식과 GCD::::Gratus' Blog

BOJ 13728 행렬식과 GCD

알고리즘 문제풀이/BOJ 2020. 1. 20. 04:00

난이도 : 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';
}

'알고리즘 문제풀이 > BOJ' 카테고리의 다른 글

BOJ 12728 n제곱 계산 / 12925 Numbers  (2) 2020.01.30
BOJ 15745 Snow Boots  (0) 2020.01.23
BOJ 13728 행렬식과 GCD  (3) 2020.01.20
BOJ 17840 피보나치 음악  (0) 2020.01.09
BOJ 1557 제곱 ㄴㄴ / BOJ 8464 Non-Squarefree Numbers  (2) 2020.01.04
BOJ 2465 줄 세우기  (0) 2019.10.31
  1. 질문자 2021.03.09 11:39 고치기 댓글

    안녕하세요 문제를 풀다 의문점이 생겨 질문드립니다. 혹시 gcd(i, N)가 아닌 gcd(i+1, N+1)인 이유를 알 수 있을까요? 전자의 경우 예제입력 3부터 맞지 않던데, 왜 각 수에 1씩 더해서 약수를 구한 값의 determinant를 구하는지 모르겠습니다..

    • Gratus 2021.03.15 21:39 신고 고치기

      헉..댓글다신걸 일주일정도 못봤네요. 요새 블로그 할 틈이 많이 안 나서인지...ㅜㅜㅜ

      너무 예전에 풀었던 문제라 잘 기억이 나지는 않지만, 기억 + 지금 다시 보면 대충 이런 느낌입니다.

      - 위 글에서 직접 보인 부분은 $d_k = d_{k-1} + d_{k-2}$ 로, 피보나치 재귀식입니다.
      - 다시 말해, 피보나치 수열처럼 귀납적으로 정의된다는 사실'만' 알고 있습니다.
      - 다른 말로 하면, $D_i$의 초항은 모른다는 말입니다. 초항은 재귀식으로 구하는게 아니니까요.
      - 즉, 초항은 직접 계산해 줘야 합니다.
      - 직접 계산해 보면 D_1 = 1, D_2 = 2인 것을 관찰하실 수 있습니다. 그걸 보고 저는 n번째 피보나치 수가 아닌 n+1번째라는걸 관찰한 것이지만, 피보나치 수열을 (0, 1, 1, 2, ...) 가 아닌 (1, 1, 2, ...) 로 정의하면 원하시는 대로 n번째가 됩니다. 왜 그렇게 하지 않았었는지는 기억이 안 나네요...

    • Gratus 2021.03.15 21:40 신고 고치기

      댓글을 읽고 다시 생각해보니 저도 fibo = {1, 1} 로 놓고 그냥 n번째로 했으면 더 깨끗했을 것 같습니다. :)



admin