百搭背心★瘋搶↘120來自星星的你也會打廣告?這畫面也太叫人垂涎欲滴!反服貿流血 法官要警交...
2013-05-12 20:04:40 人氣(389) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][循環節] 12620 - Fibonacci Sum

0
收藏
0
推薦

 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 (NM). 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)

找 循環節,最慘情況 O(100*100),但實際找到循環不到 300。
而且同是 "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;
}

12620Fibonacci Sum循環節
台長:Morris
人氣(389) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][最小表示法、窮舉] 12494 - Distinct Substring
此分類上一篇:[UVA][SlidingWindow] 11536 - Smallest Sub-Array

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文