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
//: Piotr Skotnicki
// Potyczki Algorytmiczne 2014
// ILO
#include <algorithm>
#include <array>
#include <cstdio>

using namespace std;

constexpr int N = 45;

int main()
{
    array<int, N> fib = { 1, 1 };
    for (int i = 2; i < N; ++i)
    {
        fib[i] = fib[i-1] + fib[i-2];
    }

    int t, n;
    scanf("%d", &t);

    while (t--)
    {
        scanf("%d", &n);
        bool ok = false;
        if (0 == n)
        {
            ok = true;
        }
        else
        {
            for (int a : fib)
            {
                if (n % a == 0)
                {
                    if (binary_search(begin(fib), end(fib), n / a))
                    {
                        ok = true;
                        break;
                    }
                }
            }
        }
        printf("%s\n", ok ? "TAK" : "NIE");
    }

    return 0;
}