小麦亩产一千八

jzoj 3461

题目大意

给你一个正整数序列：$a_0,a_1,a_2$……
$a_0$为1
$a_1$为p
$a_x=a_{x-1}+a_{x-2}(x>1)$
现在给你三个数$x，a_x，y$，让你判断该序列是否合法，然后求$a_y$是的值（多组数据）

输入样例

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

输出样例

2 8 -1 516847

样例解释

对于样例二，f[1]=2 时,能够满足f[3]=5，因此宰相没有撒谎，此时第5 个格子的小麦数应为f[4]=f[2]+f[3]=3+5=8.

数据范围

对于50%的数据：如果答案存在，那么$p⩽50$
对于100%的数据：$1⩽$ 数据组数$⩽10000$，$1⩽a,b⩽20$, 数据保证如果答案存在，那么$⩽p⩽1000000.$

解题思路

因为a，b很小，我们可以提前求出前二十个数的常熟项和一次项系数，我们减去常数项，如果能整除一次项系数那它就是p，然后直接求$a_y$即可

代码

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll x, y, p, xs, a[30], b[30]; int main() {a[0] = 1;b[1] = 1;for (int i = 2; i <= 20; ++i)a[i] = a[i - 1] + a[i - 2], b[i] = b[i - 1] + b[i - 2];//预处理while(~scanf("%lld%lld%lld", &x, &xs, &y)){if ((xs - a[x]) % b[x] == 0) p = (xs - a[x]) / b[x];//判断是否合法else p = 0;if (p) printf("%lld\n", a[y] + b[y] * p);//求结果else printf("-1\n");}return 0; }

总结

以上是生活随笔为你收集整理的小麦亩产一千八（jzoj 3461）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。