ZOJ 3702 Gibonacci number 找规律

In mathematical terms, the normal sequence F(n) of Fibonacci numbers is defined by the recurrence relation

F(n)=F(n-1)+F(n-2)

with seed values

F(0)=1, F(1)=1

In this Gibonacci numbers problem, the sequence G(n) is defined similar

G(n)=G(n-1)+G(n-2)

with the seed value for G(0) is 1 for any case, and the seed value forG(1) is a random integer t, (t>=1). Given thei-th Gibonacci number value G(i), and the numberj, your task is to output the value for G(j)

Input

There are multiple test cases. The first line of input is an integer T < 10000 indicating the number of test cases. Each test case contains3 integers i, G(i) and j. 1 <= i,j <=20, G(i)<1000000

Output

For each test case, output the value for G(j). If there is no suitable value fort, output -1.

Sample Input

4 1 1 2 3 5 4 3 4 6 12 17801 19

Sample Output

2 8 -1 516847

    题目是说定义一个类似于Fibonacci数列的数列Gibonacci，这个数列的计算方式和Fibonacci一样，不同的是G(0)=1，而G(1)是一个未知数t，题目则是告诉你G(i)的值，然后计算G(j)的值，其实这个题并不复杂，列几个数就会发现，G(0)=1,G(1)=t,G(2)=1+t,G(3)=1+2t,G(4)=2+3t,G(5)=3+5t......前面的系数仍然符合Fibonacci数列的规律，而这个题目的范围只到20就结束了，所以简单打个表把Fibonacci数列前面的值都算出来，再通过规律计算t的值，就能很容易得出结果了。

    下面AC代码：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int f[105]; int fibonacci() { int i; memset(f,0,sizeof(f)); f[0]=0; f[1]=1; for(i=2;i<30;i++) { f[i]=f[i-1]+f[i-2]; } return 0; } int main() { int T; int i,j; long long t; long long ans; int g; fibonacci(); scanf("%d",&T); while(T--) { scanf("%d%d%d",&i,&g,&j); t=(g-f[i-1])%f[i]; if(t==0) t=(g-f[i-1])/f[i]; else { cout<<-1<<endl; continue; } if(t<1) { cout<<-1<<endl; continue; } ans=f[j-1]+f[j]*t; cout<<ans<<endl; } return 0; }