Fibonacci
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 2960 Accepted Submission(s): 780
Problem Description
Following is the recursive definition of Fibonacci sequence:
Now we need to check whether a number can be expressed as the product of numbers in the 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
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
AC代码：
#include<cstdio>int F[50];
void FF(){F[1]=0;F[1]=1;for(int i=2;i<=45;i++){F[i]=F[i-1]+F[i-2];}
}int dfs(int n,int x){if(n<=2){return 1;}for(int i=x;i>=3;i--){if(n%F[i]==0){if(dfs(n/F[i],i)){return 1;}}}return 0;
}
int main(){int t;scanf("%d",&t);while(t--){FF();int n;scanf("%d",&n);if(dfs(n,45)==1){printf("Yes\n");}else{printf("No\n");}}return 0;
}