斐波那契数列

时间限制：1000ms 内存限制：65536K

题目描述

百度熊对数学一直都非常感兴趣。最近在学习斐波那契数列的它，向你展示了一个数字串，它称之为“斐波那契”串：

11235813471123581347112358…

聪明的你当然一眼就看出了这个串是这么构造的：

1.        先写下两位在0~9范围内的数字a, b，构成串ab；

2.        取串最后的两位数字相加，将和写在串的最后面。

上面百度熊向你展示的串就是取a = b = 1构造出来的串。

显然，步骤1之后不停地进行步骤2，数字串可以无限扩展。现在，百度熊希望知道串的第n输入

输入数据的第一行为一个整数T（1 ≤ T ≤ 1000）, 表示有T组测试数据；每组测试数据为三个正整数a, b, n（0 ≤a, b < 10, 0 < n ≤ 109）。

输出

对于每组测试数据，输出一行“Case #c: ans”（不包含引号） c是测试数据的组数，从1开始。

提示：

1.        对于第一、二组数据，串为112358134711235…

2.        对于第三组数据，串为14591459145914…

样例输入

3
1 1 2
1 1 8
1 4 8

样例输出

Case #1: 1
Case #2: 3
Case #3: 9

解题思路：

这道题肯定要找周期的，不找周期肯定会时间超限。首先我们可以把a，b情况的串列举出来（总共才81个）。我们不难发现，除了a = 0，b = 0的这种情况，就只有两种周期循环（不一定从头开始循环），分别是{1, 1, 2, 3, 5, 8, 1, 3, 4, 7}，{1, 4, 5, 9}，知道这一点我们很容易就可以写出代码了。具体见代码：

#include <stdio.h>
int s[50], temp;
int a[10] = {1, 1, 2, 3, 5, 8, 1, 3, 4, 7};
int b[4] = {1, 4, 5, 9};
int tt(int t1, int t2) {        //找到从哪个地方开始循环
    int ans = 0, i = 2, t3;
    s[0] = t1;
    s[1] = t2;
    while (1) {
        t3 = t1 + t2;
        if (t3 > 9){
            s[i++] = t1 = t3 / 10;
            s[i++] = t2 = t3 % 10;
            ans += 2;
        }
        else {
            t1 = t2;
            s[i++] = t2 = t3;
            ans++;
        }
        if (t1 == 1 && t2 == 1) {
            temp = 1;            //标记是哪种循环
            return ans;          //找到循环开始的地方
        }
        if (t1 == 1 && t2 == 4) {
            temp = 2;
            return ans;
        }
    }
}
int main() {
    int ans, t, n, t1, t2;
    scanf("%d", &t);
    for (int k = 1; k <= t; k++) {
        scanf("%d%d%d", &t1, &t2, &n);
        if (!t1 && !t2) {        //0的时候单独讨论
            printf("Case #%d: 0\n", k);
            continue;
        }
        ans = tt(t1, t2);
        if (n <= ans) {          //还没开始循环可以直接求值
            printf("Case #%d: %d\n", k, s[n - 1]);
            continue;
        }
        if (temp == 1)
            printf("Case #%d: %d\n", k, a[(n - ans - 1) % 10]);
        else printf("Case #%d: %d\n", k, b[(n - ans - 1) % 4]);
    }
    return 0;
}