[jzoj 3461]【NOIP2013模擬聯考5】小麥畝產一千八 {Fibonacci數列}

NO IMAGE

題目

Description
“有了金坷垃,肥料一袋能頂兩袋撒,小麥畝產一千八,吸收兩米下的氮磷鉀……”,話說HYSBZ(Hengyang School for Boys & Zy)學識淵博孩紙們一講到糧食,都會想起印度那個著名的故事:國王要在第一個格子裡放入一粒小麥,接下來的格子放入前面一個格子的兩倍的小麥。這樣所需小麥總數是巨大的,哪是不用金坷垃就能完成的任務?不過為了減輕國王的任務,那個下棋獲勝的宰相換了一個要求:“我只需要你在棋盤外放一粒小麥,可以將其理解為第0 個格子,然後你需要在第一個格子裡放入p粒小麥,之後每一個格子放入前兩個格子的小麥數之和的小麥,並且要滿足第a 個格子放x 粒小麥,第b 個格子放……”說到這,宰相突然發現自己說的滿足第a 個格子放x 粒小麥的情況可能不存在……欺君可是大罪啊!國王看到宰相遲遲不說,自己也煩了!我自己來算!於是國王拜託你,讓你算出第b 個格子應該放幾粒小麥。當然,就算答案不存在,你也是要告訴國王的。
Input
該題有多組資料,請讀到檔案末結束。
對於每一組資料僅一行,3 個正整數a,x,b,分別表示第a 個格子放了x 粒小麥,以及你所需要計算的是第b 個格子的小麥數量。
Output
對於每一次詢問,僅1 個整數,為第b 個格子的小麥數量,若宰相說的情況不存在,那麼請輸出-1。


解題思路

  1. 50%演算法:直接暴力列舉 p,每組資料的時間複雜度 O(ap)
  2. 100%演算法:明顯題目就是給出了一個拓展的Fibonacci” role=”presentation”>FibonacciFibonacci Fibonacci 數列,其滿足:f[0]=1,f[1]=p,f[2]=p 1,f[3]=2∗p 1……” role=”presentation”>f[0]=1,f[1]=p,f[2]=p 1,f[3]=2∗p 1……f[0]=1,f[1]=p,f[2]=p 1,f[3]=2∗p 1……f[0]=1, f[1]=p, f[2]=p 1, f[3]=2*p 1……
    原本的 Fibonacci” role=”presentation”>FibonacciFibonacciFibonacci 數列滿足:f′[0]=1,f′[1]=1,f′[2]=2,f′[3]=3……” role=”presentation”>f′[0]=1,f′[1]=1,f′[2]=2,f′[3]=3……f′[0]=1,f′[1]=1,f′[2]=2,f′[3]=3……f’[0]=1, f’[1]=1, f’[2]=2, f’[3]=3…… 設 g[i]=f[i]−f′[i]” role=”presentation”>g[i]=f[i]−f′[i]g[i]=f[i]−f′[i]g[i]=f[i]-f’[i],
    那麼其滿足 g[0]=0,g[1]=p−1,g[2]=p−1,g[3]=2p−2,g[4]=3p−3……” role=”presentation”>g[0]=0,g[1]=p−1,g[2]=p−1,g[3]=2p−2,g[4]=3p−3……g[0]=0,g[1]=p−1,g[2]=p−1,g[3]=2p−2,g[4]=3p−3……g[0]=0, g[1]=p-1, g[2]=p-1, g[3]=2p-2,g[4]=3p-3……
    已知 f[a]=x” role=”presentation”>f[a]=xf[a]=xf[a]=x,那麼在 a>0″ role=”presentation”>a>0a>0a>0 的情況下,g[a]=x−f′[a]=f′[a−1]∗(p−1)” role=”presentation”>g[a]=x−f′[a]=f′[a−1]∗(p−1)g[a]=x−f′[a]=f′[a−1]∗(p−1)g[a]=x-f’[a]=f’[a-1]*(p-1)。f′” role=”presentation”>f′f′f’我
    們可以 O(a)預處理出來,因此對於每組資料我們可以 O(1)計算出 p” role=”presentation”>ppp(答案
    不存在的情況即無法整除的情況)。之後便 O(b)” role=”presentation”>O(b)O(b)O(b)遞推計算答案就可以了。
    每組資料的時間複雜度為 O(b)” role=”presentation”>O(b)O(b)O(b)。

程式碼

#include<cstdio>
#include<algorithm>
using namespace std; 
int a,b; long long t[30],x,y; 
int main()
{
t[1]=1; t[2]=1; 
for (int i=3;i<=30;i  ) t[i]=t[i-1] t[i-2]; 
while (scanf("%d%lld%d",&a,&x,&b)==3)
{
if ((x-t[a-1])%t[a]) printf("-1\n"); 
else 
{
y=(x-t[a-1])/t[a]; 
printf("%lld\n",y*t[b] t[b-1]); 
}      
}
}