Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits
Description
“有了金坷垃，肥料一袋能顶两袋撒，小麦亩产一千八，吸收两米下的氮磷钾……”，话说HYSBZ（Hengyang School for Boys & Zy）学识渊博孩纸们一讲到粮食，都会想起印度那个著名的故事：国王要在第一个格子里放入一粒小麦，接下来的格子放入前面一个格子的两倍的小麦。这样所需小麦总数是巨大的，哪是不用金坷垃就能完成的任务？不过为了减轻国王的任务，那个下棋获胜的xdddhc换了一个要求：“我只需要你在棋盘外放一粒小麦，可以将其理解为第0 个格子，然后你需要在第一个格子里放入p粒小麦，之后每一个格子放入前两个格子的小麦数之和的小麦，并且要满足第a 个格子放x 粒小麦，第b 个格子放……”说到这，xdddhc突然发现自己说的满足第a 个格子放x 粒小麦的情况可能不存在……欺君可是大罪啊！国王看到xdddhc迟迟不说，自己也烦了！我自己来算！于是国王拜托你，让你算出第b 个格子应该放几粒小麦。当然，就算答案不存在，你也是要告诉国王的。
Input
该题有多组数据，请读到文件末结束。
对于每一组数据仅一行，3 个正整数a,x,b,分别表示第a 个格子放了x 粒小麦，以及你所需要计算的是第b 个格子的小麦数量。
Output
对于每一次询问，仅1 个整数，为第b 个格子的小麦数量，若xdddhc说的情况不存在，那么请输出-1。
Sample Input
1 1 2
3 5 4
3 4 6
12 17 8
0 1 19
Sample Output
2
8
-1
516847
【样例解释】
对于样例二，f[1]=2 时,能够满足f[3]=5，因此xdddhc没有撒谎，此时第5 个格子的小麦数应为f[4]=f[2]+f[3]=3+5=8.
Data Constraint
对于50%的数据：如果答案存在，那么p<=50
对于100%的数据：1<=数据组数<=10000，1<=a,b<=20, 数据保证如果答案存在，那么1<=p<=1000000.
解法：斐波拉契数列我们把数列中每一个值都转化为F[0]和F[1]的和，然后很容易发现规律
F[0]=1;
F[1]=F[1];
F[2]=1F[1]+1F[0];
F[3]=F[2]+F[1]=2F[1]+1F[0];
F[4]=F[3]+F[2]=3F[1]+2F[0];
F[5]=F[4]+F[3]=5F[1]+3F[0];
然后，我们就很容易发现，F[1]的系数就是第n个斐波拉契数列，而F[0]的系数就是第n-1个斐波拉契数列
因为1<=a,b<=20，所以我们可以先打一个1到20的斐波拉契数列表
F[a]=第a个斐波拉契数 * F[1]+第a-1个斐波拉契数 * F[0]
上式，题目中已经给出了F[a]和F[0]的值，然后我们就能直接算出F[1]，如果F[1]的值小于0或者不能整除第a个斐波拉契数，就输出-1，因为不能放不足一个放在第一个格子里，然后就能算出F[b]的值了
AC代码
#include<cstdio>#define ll long longusing namespace std;ll f[25]={0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765};ll a,x,b;int main() {while(scanf("%lld%lld%lld",&a,&x,&b)!=EOF) {ll nf1=x-f[a-1];if(nf1<0||nf1%f[a]) {printf("-1n");continue;}ll f1=nf1/f[a];ll fb=f[b]*f1+f[b-1];printf("%lldn",fb);}return 0;}