Description
“有了金坷垃,肥料一袋能顶两袋撒,小麦亩产一千八,吸收两米下的氮磷钾……”,话说HYSBZ(Hengyang School for Boys & Zy)学识渊博孩纸们一讲到粮食,都会想起印度那个著名的故事:国王要在第一个格子里放入一粒小麦,接下来的格子放入前面一个格子的两倍的小麦。这样所需小麦总数是巨大的,哪是不用金坷垃就能完成的任务?不过为了减轻国王的任务,那个下棋获胜的宰相换了一个要求:“我只需要你在棋盘外放一粒小麦,可以将其理解为第0 个格子,然后你需要在第一个格子里放入p粒小麦,之后每一个格子放入前两个格子的小麦数之和的小麦,并且要满足第a 个格子放x 粒小麦,第b 个格子放……”说到这,宰相突然发现自己说的满足第a 个格子放x 粒小麦的情况可能不存在……欺君可是大罪啊!国王看到宰相迟迟不说,自己也烦了!我自己来算!于是国王拜托你,让你算出第b 个格子应该放几粒小麦。当然,就算答案不存在,你也是要告诉国王的。
Input
该题有多组数据,请读到文件末结束。
对于每一组数据仅一行,3 个正整数a,x,b,分别表示第a 个格子放了x 粒小麦,以及你所需要计算的是第b 个格子的小麦数量。
对于每一组数据仅一行,3 个正整数a,x,b,分别表示第a 个格子放了x 粒小麦,以及你所需要计算的是第b 个格子的小麦数量。
Output
对于每一次询问,仅1 个整数,为第b 个格子的小麦数量,若宰相说的情况不存在,那么请输出-1。
Solutions
这题不难,挺水的。
设f[0]/f[1]、f[2]...f[a]...f[b]为第零、一、二...a...b块地小麦的数量,
我们可知:
f[0]=1;
f[2]=f[1]+f[0]=f[1]+1;
f[3]=f[2]+f[1]=2f[1]+1;
f[4]=f[3]+f[2]=3f[1]+2;
...
f[a]=f[a-1]+f[a-2]=b[a]*f[1]+b[a-1];
b[a]为斐波那契数列的第a项,b[1]=b[2]=1。
然后判断一下f[1]是否为整数,是就找出f[b]。
代码
1 var 2 a,x,b,nm:int64; 3 f:array [0..21] of int64; 4 procedure main; 5 var 6 i:longint; 7 begin 8 readln(a,x,b); 9 f[1]:=1; f[2]:=1; 10 for i:=3 to 20 do 11 f[i]:=f[i-1]+f[i-2]; 12 nm:=(x-f[a-1]) div f[a]; 13 if (x-f[a-1]) mod f[a]=0 then writeln(nm*f[b]+f[b-1]) 14 else writeln('-1'); 15 end; 16 17 begin 18 while not eof do 19 main; 20 end.