[UVA][循環節] 12620 - Fibonacci Sum
| A - Fibonacci Sum |
Background
A Fibonacci sequence is calculated by adding the previous two members of the sequence, with the first two members being both 1.
f (1) = 1; f (2) = 1; f (n > 2) = f (n - 1) + f (n - 2)
The Problem
We define a special fibonacci sequence where the maximum value in the sequence is 99. If a value in the sequence is greater than 99, a module 100 operation must be applied. The result is the following sequence:
1 1 2 3 5 8 13 21 34 55 89 44 33 77 10 87 97 84 81 65 ...
Your task is to calculate the sum of the numbers in this special fibonacci sequence between two given positions.
The Input
The input will contain several test cases. The first line indicates the number of test cases.
For each test case, the first line contains two integers: N and M (N ≤ M). N is the position of the first number that you should sum, and M is the position of the last number that you should sum. M is not greater than 1012.
The Output
For each test case, you have to output the result of the sum in a different line.
Sample Input
4
1 3
4 4
5 100
1 99999
Sample Output
4
3
5068
4933400
OMP'13
Facultad
de Informatica
Universidad
de Murcia (SPAIN)
而且同是 "1 1" 循環。
#include <stdio.h>
int f1 = 1, f2 = 1, f3;
int i, j;
int A[305] = {0,1}, cycle;
int C[305];
void build() {
for(i = 2; ; i++) {
if(f1 == 1 && f2 == 1 && i != 2)
break;
A[i] = f2;
f3 = f1 + f2;
f1 = f2, f2 = f3%100;
}
cycle = i-2;
for(i = 1; i <= cycle; i++)
C[i] = C[i-1] + A[i];
}
long long get(long long n) {
return n/cycle*C[cycle] + C[n%cycle];
}
int main() {
build();
int testcase;
long long L, R;
scanf("%d", &testcase);
while(testcase--) {
scanf("%lld %lld", &L, &R);
printf("%lld\n", get(R)-get(L-1));
}
return 0;
}