728x90
풀이
피보나치 수열에는 다음과 같은 공식이 있다.
"백준 11444, 피보나치 수 6" 코드를 사용해 a+2-1번째 피보나치 수와 1을 뺀 값에, b+2번째 피보나치 수와 1을 뺀 값을 MOD로 나눈 나머지를 출력해주면 된다.
연산에 사용되는 temp, X를 초기화 해주어야 하며, 나머지간의 연산이기 때문에 음수가 나올 수 있다는 점을 유의하자.
소스코드
#include <stdio.h>
#define ll long long
const int MOD = 1e9;
ll X[2][2] = {0, 1, 1, 1};
void fibo(ll result[][2], ll f[][2]){
int temp[2][2] = {0,};
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
temp[i][j] += (result[i][k]*f[k][j]) %MOD;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
result[i][j] = temp[i][j] %MOD;
}
int main(){
ll n1, n2, result = 0;
scanf("%lld %lld", &n1, &n2);
ll n = n1+1;
for (int op = -1; op < 2; op+= 2){
ll temp[2][2] = {1, 0, 0, 1};
while (n){
if (n & 1) fibo(temp, X);
fibo(X, X);
n >>= 1;
}
result = op*(result + temp[1][0]-1) %MOD;
X[0][0] = 0;
X[0][1] = X[1][0] = X[1][1] = 1;
n = n2+2;
}
printf("%lld", (result+MOD)%MOD);
}
출처 및 참고자료
2086번: 피보나치 수의 합
첫째 줄에 a와 b(1≤a≤b≤9,000,000,000,000,000,000)이 주어진다.
www.acmicpc.net
피보나치 수 - 위키백과, 우리 모두의 백과사전
피보나치 수를 이용한 사각형 채우기 수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8
ko.wikipedia.org
[백준 11444] 피보나치 수 6 [C]
풀이 다음과 같이 행렬을 이용해 피보나치 수를 구할 수 있다. "백준 10830, 행렬 제곱" 코드를 이용해 완성했다. 소스코드 #include #define ll long long const int MOD = 1e9 + 7; ll X[2][2] = {0, 1, 1, 1}..
kyr-db.tistory.com
728x90
'PS > Baekjoon Online Judge' 카테고리의 다른 글
[백준 11442] 홀수번째 피보나치 수의 합 [C] (0) | 2021.08.23 |
---|---|
[백준 11778] 피보나치 수와 최대공약수 [C] (0) | 2021.08.21 |
[백준 11444] 피보나치 수 6 [C] (0) | 2021.08.21 |
[백준 10830] 행렬 제곱 [C] (0) | 2021.08.21 |
[백준 13172] Σ [C] (0) | 2021.08.20 |