[백준 7677] Fibonacci [C]

백준 - 7677

---

풀이

n이 -1일 때까지 n번째 피보나치 수를 출력해주면 된다.

"백준 11444, 피보나치 수 6" 코드를 사용해 풀이했다.

10,000으로 나눈 나머지로 계산해 출력하면 된다.

---

소스코드

#include <stdio.h>
#define ll long long
#define MOD 10000
ll X[2][2] = {0, 1, 1, 1};

void fibo(ll result[][2], ll f[][2]){
    ll 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(){
    while(1){
        ll n;
        scanf("%lld", &n);
        if (n == -1) break;
		
        ll result[2][2] = {1, 0, 0, 1};
        while (n){
            if (n & 1) fibo(result, X);
            fibo(X, X);
            n >>= 1;
        }
        printf("%lld\n", result[1][0]);
        X[0][0] = 0;
        X[0][1] = X[1][0] = X[1][1] = 1;
    }
}

---

출처 및 참고자료

7677번: Fibonacci

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