Problem Description Following is the recursive definition of Fibonacci sequence: Fi=???01Fi?1+Fi?2i = 0i = 1i > 1 Now we need to check whether a number can be expressed as the product of numbers in the Fibonacci sequence.

?

Input There is a number?T?shows there are?T?test cases below. (T≤100,000) For each test case , the first line contains a integers n , which means the number need to be checked.? 0≤n≤1,000,000,000

?

Output For each case output "Yes" or "No".

?

Sample Input 3 4 17 233

?

Sample Output Yes No Yes

?

Source BestCoder Round #28 題意：判斷一個數能否由任意個菲波那媞數相乘得到，能的話輸出“Yes”，否則輸出“No” 思路：首先要處理菲波那媞數組，然后用一個隊列來實現菲波那媞數的相乘，用一個map數組來標記。具體看代碼

?

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<stdlib.h> 6 #include<algorithm> 7 #include<queue> 8 #include<map> 9 using namespace std; 10 #define N 46 11 #define ll long long 12 ll f[N]; 13 map<ll,bool>mp; 14 void init() 15 { 16 mp.clear(); 17 queue<ll>q; 18 f[0]=0; 19 f[1]=1; 20 mp[0]=true; 21 mp[1]=true; 22 q.push(0); 23 q.push(1); 24 for(int i=2;i<N;i++) 25 { 26 f[i]=f[i-1]+f[i-2]; 27 mp[f[i]]=true; 28 q.push(f[i]); 29 } 30 while(!q.empty()) 31 { 32 ll tmp=q.front(); 33 q.pop(); 34 for(int i=0;i<N;i++) 35 { 36 ll cnt=tmp*f[i]; 37 if(cnt>1000000000L) 38 break; 39 if(mp[cnt]) continue; 40 mp[cnt]=true; 41 q.push(cnt); 42 } 43 } 44 45 } 46 int main() 47 { 48 init(); 49 int t; 50 scanf("%d",&t); 51 while(t--) 52 { 53 ll n; 54 scanf("%I64d",&n); 55 if(mp[n]==true) 56 printf("Yes\n"); 57 else 58 printf("No\n"); 59 60 } 61 return 0; 62 } View Code

?

轉載于:https://www.cnblogs.com/UniqueColor/p/4743704.html

總結

以上是生活随笔為你收集整理的hdu 5167 Fibonacci(预处理)的全部內容，希望文章能夠幫你解決所遇到的問題。

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