1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

#define MAXN   1000000000
#define K      50

typedef vector<long> vl_t;
typedef vector<long>::iterator vl_it;
typedef vector<long>::const_iterator vl_cit;

typedef set<long> sl_t;
typedef set<long>::iterator sl_it;
typedef set<long>::const_iterator sl_cit; 

void genfibo(std::vector<long> & v) 
{
   v.clear();
   v.reserve(K);
   long a = 0, b = 1, tmp;
   v.push_back(a);
   v.push_back(b);
   while (b < MAXN) {
      tmp = a + b;
      a = b;
      b = tmp;
      v.push_back(b);
   }
}

void genprods(const vl_t & fibo_nums, sl_t & s)
{
   s.clear();
   if (fibo_nums.size() < 1)
      return;
 
   for (vl_cit i = fibo_nums.begin(); i != fibo_nums.end(); ++i)
   {
      bool cont = true;
      for (vl_cit j = i; cont && j != fibo_nums.end(); ++j)
      {
         long tmp = *i * *j;
         if (tmp >= 0 && tmp < MAXN)
            s.insert(tmp);
         else
            cont = false;
      }
   }
}

int main(int argc, char const *argv[])
{
   ios_base::sync_with_stdio(0);

   vl_t fibo_nums;
   sl_t prods;
   genfibo(fibo_nums);
   genprods(fibo_nums, prods);

   int t;
   cin >> t;

   for (int i = 0; i < t; ++i)
   {
      int x;
      cin >> x;
      if (prods.find(x) != prods.end())
         cout << "TAK" << endl;
      else
         cout << "NIE" << endl;
   }

   return 0;
}