[백준 2086] 피보나치 수의 합 [C]

백준 - 2086

---

풀이

피보나치 수열에는 다음과 같은 공식이 있다.

위키백과 - 피보나치 수

"백준 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번: 피보나치 수의 합

피보나치 수 - 위키백과, 우리 모두의 백과사전

[백준 11444] 피보나치 수 6 [C]