每天一算法（du熊学斐波那契I）百度之星限时做。。

Problem Description

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

11235813471123581347112358........

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

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

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

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

显然，步骤1之后不停地进行步骤2，数字串可以无限扩展。现在，du熊希望知道串的第n位是什么数字。

Input

输入数据的第一行为一个整数T（1 <= T <= 1000）, 表示有T组测试数据；

每组测试数据为三个正整数a, b, n（0 <= a, b < 10, 0 < n <= 10^9）。

Output

对于每组测试数据，输出一行“Case #c: ans”（不包含引号）

c是测试数据的组数，从1开始。

Sample Input

3

1 1 2

1 1 8

1 4 8

Sample Output

Case #1: 1

Case #2: 3

Case #3: 9

Hint

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

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

一开始关键做，，没想到更好的方法，，应该不用这么麻烦的。。

下边贴出自己做的程序代码，，望各位指点。。

#include <iostream>#include <vector>using namespace std;int inttochar(int x,vector<int> &timeresult){int num=0;vector<int> TIMe;while (0 != x){int tim = x%10;TIMe.push_back(tim);x = x/10;num++;}int k = TIMe.size();for (vector<int>::size_type i = TIMe.size()-1;i>0;i--){timeresult.push_back(TIMe[i]);}timeresult.push_back(TIMe[0]);//TIMe.clear();return num;}int main(){int num;cin>>num;int **Ptr;Ptr = (int **)new int *[num];for (int i = 0;i<num;i++){Ptr[i] = new int[3];}for (int i = 0;i<num;i++){for (int j = 0;j<3;j++){cin>>Ptr[i][j];}}int *Result = new int[num];for (int i = 0;i<num;i++){vector<int> timresult;int first = Ptr[i][0];int Second = Ptr[i][1];int number = 0;number += inttochar(first,timresult);number += inttochar(Second,timresult);while (number<Ptr[i][2]){int third = timresult[timresult.size()-1]+timresult[timresult.size()-2];number += inttochar(third,timresult);//first = Second;//Second = third;}Result[i] = timresult[Ptr[i][2]-1];timresult.clear();}for (int i = 0;i<num;i++){//printf("Case#%d:%d",i+1,Result[i]);cout<<"Case #"<<i+1<<": "<<Result[i]<<endl;cout<<endl;}//cout<<Fabonacci(6);return 0; }