[Gold II] 피보나치 수 6 - 11444

문제 링크

문제 링크

성능 요약

메모리: 2024 KB, 시간: 0 ms

문제 설명

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 F_n = F_n-1 + F_n-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

코드

#include <iostream>
#include <vector>

using namespace std;

const long long MOD = 1000000007;  // 피보나치 수를 나눌 큰 소수

// 2x2 행렬의 곱셈을 수행하는 함수
vector<vector<long long>> matrixMultiply(const vector<vector<long long>>& a, const vector<vector<long long>>& b) {
	vector<vector<long long>> result(2, vector<long long>(2, 0));  // 결과 행렬을 초기화
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % MOD;  // 행렬 곱셈 후 MOD 연산
			}
		}
	}
	return result;
}

// 2x2 행렬을 n번 곱하는 함수
vector<vector<long long>> matrixPower(vector<vector<long long>> base, long long exp) {
	vector<vector<long long>> result = { {1, 0}, {0, 1} };  // 항등 행렬로 초기화
	while (exp > 0) {
		if (exp % 2 == 1) {  // 지수가 홀수이면
			result = matrixMultiply(result, base);  // 결과에 현재 행렬을 곱함
		}
		base = matrixMultiply(base, base);  // 행렬을 제곱
		exp /= 2;  // 지수를 반으로 줄임
	}
	return result;
}

// n번째 피보나치 수를 계산하는 함수
long long fibonacci(long long n) {
	if (n == 0) return 0;
	vector<vector<long long>> base = { {1, 1}, {1, 0} };  // 피보나치 행렬 초기값 설정
	vector<vector<long long>> result = matrixPower(base, n - 1);  // 행렬 거듭제곱을 통해 피보나치 수 계산
	return result[0][0];  // 피보나치 수 반환
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	long long dist;
	cin >> dist;

	cout << fibonacci(dist) << "\n";  // n번째 피보나치 수 출력

	return 0;
}