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
78
79
80
81
82
#include <iostream>
#include <cmath>

using namespace std;

//a utility function that returns true if x is a perfect square
bool isPerfectSquare(int x){
    //a perfect square is an integer that is the square of an integer
    //in other words, it is the product of some integer with itself
    int s = sqrt(x);
    return (s*s == x);
}

//return true if n is a Fibonacci Number, else false
bool isFibonacci(int n){
    //n is Fibonacci if one of 5*n*n + 4 or 5*n*n - 4 or both is a perfect square
    //according to the wiki's website:
    //http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers
    return isPerfectSquare(5*n*n + 4) || isPerfectSquare(5*n*n - 4);
}

int fibDynamic(int n){
    if (n < 2) return n;
    int i;
    int *tab = new int[n+1];
    tab[0] = 0;
    tab[1] = 1;
    for (i = 2; i <= n; i++){
        tab[i] = tab[i-1] + tab[i-2];
    }
    int zmienna= tab[n];
    delete []tab;
    return zmienna;
}

bool check(int number){
    int k = 0;

    if (isFibonacci(number)){
        return true;
    }
    else if ((number % 2 == 0) && isFibonacci(number/2)) return true;
    else{
        for (int i = 4; k < number/2; i++){
        	k = fibDynamic(i);
            if (number % k == 0){
            	   // cout << "toliczba z petli " << number/k << endl;
                if ( isFibonacci(number/k) ){
                    return true;
                }break;
            }
        }
        return false;
    }
    
}

int main(){

    int cases, number;

   /* for (int i = 1; i <= 10; i++){
        isFibonacci(i) ? cout << i << " is a Fibonacci Number \n" :
                         cout << i << " is NOT a Fibonacci Number \n";
    }
    return 0;
    }*/
    
   /* for (int i = 0; i < 10; i++){
    	    cout << fibDynamic(i) << " ";
    }
    */
    cin >> cases;

    for (int i = 0; i < cases; i++){
        cin >> number;
        if (check(number)) cout << "TAK";
        else cout << "NIE";
        cout << endl;
    }
    return 0;
}