HDU 5167(map + 暴力)

题意：给出一个数n，问n能否是斐波那契数列中数的乘积

先刷选斐波那契数列，然后就枚举

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <queue>
 4 #include <map>
 5 #include <iostream>
 6 using namespace std;
 7 typedef long long LL;
 8 const LL Max = 1000000000;
 9 LL num[50];
10 map<LL, bool> m;
11 void init()
12 {
13     queue<LL> q;
14     m[0] = true;
15     m[1] = true;
16     num[0] = 0;
17     num[1] = 1;
18     for (int i = 2; i < 46; i++)
19     {
20         num[i] = num[i - 1] + num[i - 2];
21         q.push(num[i]);
22         m[ num[i] ] = true;
23     }
24     while (!q.empty())
25     {
26         int temp =  q.front();
27         q.pop();
28         for (int i = 1; i < 46; i++)
29         {
30             LL res = temp * num[i];
31             if (res > Max)
32                 break;
33             if (m[ res ])
34                 continue;
35             m[ res ] = true;
36             q.push(res);
37         }
38     }
39 
40 }
41 int main()
42 {
43     init();
44     int test, n;
45     scanf("%d", &test);
46     while (test--)
47     {
48         scanf("%d", &n);
49         if (m[ n ])
50             printf("Yes
");
51         else
52             printf("No
");
53     }
54     return 0;
55 }

View Code