Problem DescriptionFollowing 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.
InputThere 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 OutputFor each case output “Yes” or “No”. Sample Input3 4 17 233 Sample OutputYes No Yes SourceBestCoder Round #28 题意:判断一个数能否由任意个菲波那媞数相乘得到,能的话输出“Yes”,否则输出“No”思路:首先要处理菲波那媞数组,然后用一个队列来实现菲波那媞数的相乘,用一个map数组来标记。具体看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<stdlib.h>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
#define N 46
#define ll long long
ll f[N];
map<ll,bool>mp;
void init()
{
mp.clear();
queue<ll>q;
f[]=;
f[]=;
mp[]=true;
mp[]=true;
q.push();
q.push();
for(int i=;i<N;i++)
{
f[i]=f[i-]+f[i-];
mp[f[i]]=true;
q.push(f[i]);
}
while(!q.empty())
{
ll tmp=q.front();
q.pop();
for(int i=;i<N;i++)
{
ll cnt=tmp*f[i];
if(cnt>1000000000L)
break;
if(mp[cnt]) continue;
mp[cnt]=true;
q.push(cnt);
}
} }
int main()
{
init();
int t;
scanf("%d",&t);
while(t--)
{
ll n;
scanf("%I64d",&n);
if(mp[n]==true)
printf("Yes\n");
else
printf("No\n"); }
return ;
}