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

题意：判断一个数n是不是Fibonacci序列中数的乘积（可以是同一个数）。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int N=1e6+10;const int INF=0x3f3f3f3f;const int MOD=1e9;typedef long long LL;LL n, a[60];int k, flag;void Solve() ///打表，并找到满足题意的最大的Fibonacci数的下标k{ int i; a[0] = 0; a[1] = 1; for (i = 2; i <= 50; i++) { a[i] = a[i-1]+a[i-2]; if (a[i] >= MOD) { if (a[i] > MOD) i--; k = i; break; } }}void DFS(int num, LL m){ int i; if (m == 1) flag = 1; if (flag == 1) return ; if (num < 3) return ; if (m % a[num] == 0) DFS(num, m/a[num]); DFS(num-1, m);}int main (){ int T; Solve(); scanf("%d", &T); while (T--) { scanf("%lld", &n); flag = 0; if (n == 0) { printf("Yes\n"); continue; } DFS(k, n); if (flag == 1) printf("Yes\n"); else printf("No\n"); } return 0;}