백준 2749번: 피보나치 수 3

www.acmicpc.net/problem/2749

2749번: 피보나치 수 3

---

전에 올렸던 피보나치 수 6, Immortal Porpoises와 거의 동일한 문제입니다.

( 백준 11524번: Immortal Porpoises , 백준 11444번: 피보나치 수 6 )

 

차이점으로는 modulo 값이 $ 10^{6} $ 으로 상당히 작다는 점입니다.

 

따라서 피사노 주기가 $ 15\times 10^{5} $ 이므로 이를 활용하여 코드를 짤 수 있습니다.

(피사노 주기란, 피보나치 수의 mod 값의 주기를 말합니다.)

 

먼저 정석적으로, $ O \left ( logN \right ) $ 으로 구하는 코드입니다.

 

#include <stdio.h>

typedef struct {
	long long array[2][2];
} Matrix;

Matrix matrix_multiply_modular (Matrix A, Matrix B, int M);
Matrix matrix_power_modular (Matrix A, long long k, int M);

int main() {
	
	Matrix Base;
	Base.array[0][0] = Base.array[0][1] = Base.array[1][0] = 1, Base.array[1][1] = 0;
	
	long long n;
	scanf("%lld", &n);
	
	Matrix Fibonacci = matrix_power_modular (Base, n, 1000000);
	printf("%lld", Fibonacci.array[0][1]);
	
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, int M) {
	Matrix result;
	int i, j, k;
	for (i = 0; i < 2; i++) {
		for (j = 0; j < 2; j++) {
			result.array[i][j] = 0;
			for (k = 0; k < 2; k++) {
				long long temp = (A.array[i][k] * B.array[k][j] ) % M;
				result.array[i][j] = (result.array[i][j] + temp) % M;
			}
		}
	}
	return result;
}

Matrix matrix_power_modular (Matrix A, long long k, int M) {
	Matrix result;
	result.array[0][0] = 1, result.array[0][1] = 0, result.array[1][0] = 0, result.array[1][1] = 1;
	while (k > 0) {
		if (k & 1) {
			result = matrix_multiply_modular (result, A, M);
		}
		A = matrix_multiply_modular (A, A, M);
		k >>= 1;
	}
	return result;
}

 

(C11, 1116KB, 0ms, 제출번호 25804935)

---

그리고 피사노 주기를 이용하는 코드입니다.

 

#include <stdio.h>
#include <stdlib.h>

int Fibonacci_mod_million (long long N);

int main() {
	long long n;
	scanf("%lld", &n);
	printf("%d", Fibonacci_mod_million (n));
	return 0;
}

int Fibonacci_mod_million (long long N) {
	int* array = (int*)malloc(sizeof(int)*1500010);
	array[0] = 0;
	array[1] = 1;
	int i;
	for (i = 0; i <= 1500000; i++) {
		array[i+2] = (array[i] + array[i+1]) % 1000000;
	}
	int result = array[N % 1500000];
	free(array);
	return result;
}

 

(C11, 6976KB, 12ms, 제출번호 25397267)

---

피사노 주기를 이용하여 풀 수 있지만

 

피사노 주기 자체가 생소한 소재이므로 이전에 접해보지 않았다면 그 방법으로는 풀기 어려웠을 것 같습니다.

 

근데 골드2는 아무리 봐도 좀 과하네요.