백준 2086 (C++) 피보나치 수의 합

최초 업로드: 2025-08-07 08:53:13

최근 수정 시간: 2025-08-07 08:53:42

게시자: rlatjwls3333

카테고리: 백준

# [Gold I] 피보나치 수의 합

[문제 링크](https://www.acmicpc.net/problem/2086)

## 문제 설명

제 1항과 제 2항을 1이라 하고, 제 3항부터는 앞의 두 항의 합을 취하는 수열을 피보나치(fibonacci) 수열이라고 한다. 예를 들어 제 3항은 2이며, 제 4항은 3이다.

피보나치 수열의 a번째 항부터 b번째 항까지의 합을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으므로 마지막 아홉 자리만을 구하도록 한다. 즉 1,000,000,000으로 나눈 나머지를 구하면 된다.

## 입력

첫째 줄에 a와 b이 주어진다.

## 출력

첫째 줄에 구한 합을 출력한다.

## 풀이
#### 피보나치 수열에서 1번 항부터 n번 항까지의 합이 n+2번째 항 - 1 이라는 것과 피보나치 수열을 행렬곱으로 빠르게 구할 수 있다는 것을 이용하여 풀었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const ll MOD = 1e9;

vvll square(vvll a, vvll b) {
 vvll ret = {
 {0, 0},
 {0, 0},
 };
 for(int i=0;i<2;i++) {
 for(int j=0;j<2;j++) {
 for(int k=0;k<2;k++) {
 ret[i][j] += (a[i][k] * b[k][j]);
 }
 ret[i][j] %= MOD;
 }
 }
 return ret;
}

ll fibo(ll n) {
    vvll ret = {
        {1, 0},
        {0, 1},
    };
    vvll a = {
        {1, 1},
        {1, 0},
    };
    while(n) {
        if(n & 1) {
            ret = square(ret, a);
        }
        n>>=1;
        a = square(a, a);
    }
    return ret[1][0];
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 ll a, b; cin >> a >> b;
 // fibo(1) ~ fibo(n)의 합 : fibo(n+2)-1
 cout << (fibo(b+2) - fibo(a+1) + MOD) % MOD;
}
```