취미로 코딩하기

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

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

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

먼저 주어진 형태의 \(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;
}