2086 - 피보나치 수의 합
본문
제 1항과 제 2항을 $1$이라 하고, 제 3항부터는 앞의 두 항의 합을 취하는 수열을 피보나치(fibonacci) 수열이라고 한다. 예를 들어 제 3항은 $2$이며, 제 4항은 $3$이다.
피보나치 수열의 $a$번째 항부터 $b$번째 항까지의 합을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으므로 마지막 아홉 자리만을 구하도록 한다. 즉 $1\,000\,000\,000$으로 나눈 나머지를 구하면 된다.
입력
첫째 줄에 $a$와 $b$이 주어진다.
출력
첫째 줄에 구한 합을 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 128MB |
- $1 \leq a \leq b \leq 9\,000\,000\,000\,000\,000\,000$
풀이
피보나치 수열 함수를 $f_x$라고 하면, 문제에서 원하는 답은 $\sum_{i=a}^{b} f_i$가 될 것이다. 피보나치는 이전 값을 계속 이용하니까 기본적으로 수 하나당 $O(N)$에 구할 수 있는데, 문제는 가능한 수의 범위가 최대 900경이라는 것. 당연히 $O(N)$으로는 구할 수 없다.
다행히도, 우리는 피보나치 수를 $O(\log N)$에 구하는 방법을 알고 있다. 아래 식을 응용하는 것.
\[\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{N} = \begin{pmatrix} f_{N+1} & f_{N} \\ f_{N} & f_{N-1} \end{pmatrix}\]그래서, 우리는 저 행렬의 제곱을 빠르게 구할 수 있다면 피보나치 수를 빠르게 구할 수 있다는 것을 의미한다. 그리고 제곱은, 분할 정복을 이용하면 $O(\log N)$으로 구할 수 있다.
문제는 구해야하는 수의 개수다. 구해야하는 수의 최대 범위는 900경까지. 피보나치 수 하나를 빠르게 구할 수 있더라도 900경의 수는 모두 구할 수 없다. 수식을 정리해야할 것이다.
피보나치 수는 2개의 연속된 수를 묶어서 더하면, 그 다음 피보나치 수와 그 값이 같다는 점을 이용할 수 있다. 그래서, 식을 정리하다 보면 여러 개의 피보나치 수의 합을 더 적은 수의 피보나치 수의 합으로도 표현할 수 있을 것 같다. 그래서 예시를 통해 식을 계산해보자.
첫 번째 예시로, 3 10이 입력으로 주어진다고 해보자. 그러면 구하는 식은 $\sum_{i=3}^{10} f_i$가 된다. 수의 개수가 짝수이므로 2개씩 짝을 지어 묶으면 $\sum_{i=3}^{10} f_i = f_{11} + f_9 + f_7 + f_5$가 된다. 여기에 $0 = f_{10} - f_{10}$을 더해보자.
식을 정리했더니, 8개의 피보나치 수의 합을 2개의 피보나치 수만을 계산하면 구할 수 있다는 것을 알 수 있다. 한번만 더 해보자. 이번에는 아까 예시에서 $f_2$를 추가하자. 그러면 최종 결과는 $\sum_{i=2}^{10} f_i = f_{12} - f_4 + f_2$가 된다. $f_4$와 $f_2$는 서로 묶일 수 없으므로 그대로 두자.
즉 주어지는 수의 개수가 짝수인지 홀수인지에 따라 구해야하는 수의 개수가 달라짐을 알 수 있다. 수의 개수가 짝수인 경우 $\sum_{i=a}^{b} f_i = f_{b+2} - f_{a+1}$로 계산할 수 있었고, 수의 개수가 홀수인 경우는 $\sum_{i=a}^{b} f_i = f_{b+2} - f_{a+2} + f_{a}$로 계산할 수 있다. 결국 수의 개수가 아무리 많아도 피보나치 수는 최대 3개만 구하면 된다. 이건 시간 안에 충분히 돌기 때문에, 피보나치 수를 구하는 방법만 확실하게 구현하면 답을 얻을 수 있다.
- 참고 알고리즘 : 피보나치 수열
코드
사용 언어 : C
최종 수정일 : 2023 / 4 / 30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
typedef long long ll;
const ll MOD = (ll)(1e9);
void multiply(ll a[2][2], ll b[2][2]) {
ll t1 = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD;
ll t2 = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD;
ll t3 = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD;
ll t4 = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD;
a[0][0] = t1, a[0][1] = t2;
a[1][0] = t3, a[1][1] = t4;
return;
}
void power(ll matrix[2][2], ll x) {
if (x == 0 || x == 1) {
return;
}
power(matrix, x / 2);
multiply(matrix, matrix);
if (x % 2 == 1) {
ll next[2][2] = { {1, 1}, {1, 0} };
multiply(matrix, next);
}
return;
}
ll f(ll x) {
ll matrix[2][2] = { {1, 1}, {1, 0} };
if (x == 0) {
return 0;
}
power(matrix, x - 1);
return matrix[0][0];
}
int main() {
ll a, b;
scanf("%lld %lld", &a, &b);
ll retval = 0;
if ((b - a) % 2 == 1) {
retval = f(b + 2) - f(a + 1);
} else {
retval = f(b + 2) - f(a + 2) + f(a);
}
printf("%lld", (retval + MOD) % MOD);
return 0;
}