이제 피보나치 수 자체만을 구하는 게 아니고 조금씩 변형이 되고 있습니다.
이 문제에서는 다음과 같은 성질을 알고 있어야 합니다.
$ 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)
'분할 정복을 이용한 거듭제곱 > 행렬 거듭제곱' 카테고리의 다른 글
백준 2086번: 피보나치 수의 합 (0) | 2021.01.29 |
---|---|
백준 11238번: Fibo (0) | 2021.01.29 |
백준 13075번: Fibonacci Sequence (0) | 2021.01.29 |
백준 2749번: 피보나치 수 3 (0) | 2021.01.29 |
백준 11524번: Immortal Porpoises (0) | 2021.01.29 |