백준 11778번: 피보나치 수와 최대공약수

www.acmicpc.net/problem/11778

11778번: 피보나치 수와 최대공약수

---

이제 피보나치 수 자체만을 구하는 게 아니고 조금씩 변형이 되고 있습니다.

 

이 문제에서는 다음과 같은 성질을 알고 있어야 합니다.

 

$ GCD \left ( F_{a}, F_{b}\right ) = F_{GCD \left ( a, b \right )} $

 

최대공약수, GCD를 구하는 방법은 유클리드 호제법을 이용하면 충분합니다.

 

long long GCD (long long x, long long y) {
	long long temp;
	while (y > 0) {
		temp = x % y;
		x = y;
		y = temp;
	}
	return x;
}

 

이렇게 구현한 유클리드 호제법은 최악의 경우 n'비트' 정수에 대해 $ O \left ( n \right ) $ 이라고 어디서 주워들었는데, 확실하진 않습니다.

 

아무튼, long long 범위에서 이 함수는 충분히 빠르게 작동한다고 볼 수 있습니다.

 

이 GCD함수를 이용하여 구현한 코드는 다음과 같습니다.

 

#include <stdio.h>

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

long long GCD (long long x, long long y);

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

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

long long GCD (long long x, long long y) {
	long long temp;
	while (y > 0) {
		temp = x % y;
		x = y;
		y = temp;
	}
	return x;
}

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

---