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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

int main(int argc, char ** argv) {
  std::vector<long long> fib; 
  long long MAX = 1000000000;
  long long prev = 0, actual = 1, temp;
  fib.push_back(actual);
  while (actual <= MAX) {
    temp = actual;
    actual += prev;
    fib.push_back(actual);
    prev = temp;
  }

  long long input, sqr;

  short num;
  std::cin >> num;
  for (int i = 0; i < num; i++) {
  std::cin >> input;
    sqr = sqrt(input) + 1;

    if (input == 0) {
      std::cout << "TAK" << std::endl;
      continue;
    }
    bool cond = 1;
    for (std::vector<long long>::iterator it = fib.begin(); it != fib.end() && *it <= sqr && cond; ++it) {
      if (input % *it == 0) {
        long long res = input / *it;
        if (find(fib.begin(), fib.end(), res) != fib.end()) {
          std::cout << "TAK" << std::endl;
          cond = 0;
        }
      }
    }
    if (cond) std::cout << "NIE" << std::endl;
  }

  return 0;
}