백준 11238번: Fibo

www.acmicpc.net/problem/11238

11238번: Fibo

---

슬슬 지겨워지는 피보나치 수입니다.

 

본문에서는 피보나치 수를 재귀적으로 구하는 방법, 일반화된 피보나치 수 공식에, 추가적으로 성질 두 가지를 소개하고 있습니다.

 

첫번째 성질은 피보나치 수의 합에 관한 것인데, 이는 나중에 다룰 문제들에서 볼 것입니다.

 

두번째 성질은 피보나치 수와 최대공약수에 관한 성질인데, 아마 출제 의도는 이걸 보고 추론하라는 것 같습니다.

 

$ F_{n}|F_{kn} $ where $ k = 0, 1, 2, \cdots $

 

그러나 우리는 이미 이전 글에서 이 문제가 요구하는 바를 파악한 적 있습니다. (백준 11778번: 피보나치 수와 최대공약수)

 

따라서 똑같은 방법으로 코드를 작성해주면 충분합니다.

 

#include <stdio.h>

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

int GCD (int a, int b);

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

int main() {
	
	Matrix Base;
	Base.array[0][0] = 1, Base.array[0][1] = 1, Base.array[1][0] = 1, Base.array[1][1] = 0;
	
	int T;
	scanf("%d", &T);
	
	Matrix Fibonacci;
	int N, M;
	
	int i;
	for (i = 0; i < T; i++) {
		scanf("%d %d", &N, &M);
		Fibonacci = matrix_power_modular (Base, GCD(N, M), 1000000007);
		printf("%lld\n", Fibonacci.array[0][1]);
	}
	
	return 0;
}

int GCD (int a, int b) {
	long long temp;
	while (b != 0) {
		temp = a % b;
		a = b;
		b = temp;
	}
	return a;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, long long M) {
	Matrix result;
	int i, j, k;
	for (i = 0; i <= 1; i++) {
		for (j = 0; j <= 1; j++) {
			result.array[i][j] = 0;
			for (k = 0; k <= 1; 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, int k, long long 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, 제출번호 25807214)

---

채점 속도도 그렇고, 걸린 시간도 그렇고, 정말 최소한의 데이터만 넣어놓은 듯 합니다.

 

그렇다고 해도 어째서인지 골드1을 부여받은 데다 영어라서, 정말 인기 없는 문제였습니다.