小麥畝產一千八

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）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。