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
#include <stdio.h>
using namespace std;

int main(int argc, char** argv) {
    int amountOfInputNumbers;
    /* It is faster to create constant table of Fibonnaci numbers < 10^9, 
       than to calculate Fibonacci numbers every time */
    int fibonacciFrom2to44[43] = {
        1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,
        17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,
        2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,
        102334155,165580141,267914296,433494437,701408733
    };
    
    scanf("%d",&amountOfInputNumbers);
    for(int i=0; i<amountOfInputNumbers; i++){
        int currentNumber;
        scanf("%d",&currentNumber);
        if(currentNumber != 0){
            int smallerIndex = 0;
            int biggerIndex = 42;
            int multiplication;
            do{
                multiplication = fibonacciFrom2to44[smallerIndex] * fibonacciFrom2to44[biggerIndex];
                if(multiplication > currentNumber)
                    biggerIndex --;
                else if (multiplication < currentNumber)
                    smallerIndex ++;
                else 
                    printf("TAK\n");
            }
            while ( (smallerIndex <= biggerIndex) && (multiplication != currentNumber) );
            if(multiplication != currentNumber){
                printf("NIE\n");
            }
        }
        else printf("TAK\n");
    }
    return 0;
}