[BOJ 13728 // C++] 행렬식과 GCD

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 13728번 문제인 행렬식과 GCD이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/13728 

13728번: 행렬식과 GCD

 

먼저 주어진 형태의 $n$행 $n$열($n>2)$ tridiagonal matrix의 determinant $D_n$를 구하는 점화식을 유도해보자. 이 점화식은 먼저 우하단 원소를 기준으로 행방향으로 여인수 전개(Cofactor Expansion)을 하고, 그 다음으로 $n-1$행 $n-1$열 행렬꼴이 아닌 다른 행렬을 우하단 원소를 기준으로 열방향으로 여인수 전개하는 것으로 구할 수 있다. 구체적으로, 다음과 같은 점화식을 얻는다:

$D_n=D_{n-1}+D_{n-2}$

한편 $D_1=1$, $D_2=2$임은 어렵지 않게 계산할 수 있다. 따라서 $D_n=F_{n+1}$이 성립한다. 여기서 $F_n$은 $n$번째 피보나치 수이다.

한편, $gcd(F_i,F_j)=F_{gcd(i,j)}$임은 well-known 지식이다. 이를 활용해 $n+1$번째까지의 피보나치 수(를 1000000007로 나눴을 때의 나머지)를 미리 구해두고 각 최대공약수번째 수를 하나하나 직접 더해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int gcd(int x, int y) {
	if (y) return gcd(y, x % y);
	return x;
}

int F[100002];
int N, ans;

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

	F[1] = 1;
	for (int i = 2; i < 100002; i++) {
		F[i] = F[i - 1] + F[i - 2];
		if (F[i] > 1000000006) F[i] -= 1000000007;
	}
	cin >> N; N++;
	for (int i = 2; i <= N; i++) {
		int g = gcd(i, N);
		ans += F[g];
		if (ans > 1000000006) ans -= 1000000007;
	}

	cout << ans;
}