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
/*
for (max 10 razy)
{
	2. wybieranie l. fibb. minimalnie mniejszej od badanej liczby
	
	3. sprawdzanie, czy są dwie talkie liczby fibb, które po pomnożeniu wynoszą tyle, co podana liczba
	
	4. wpisanie odp. do tabelki z odp.
}

*/

#include <iostream>
using namespace std;
unsigned long int tab_fib[45] = {0, 1, 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};
int dana[10];
bool wynik[10] = {false,false,false,false,false,false,false,false,false,false};
int maksymalna = 0;
int id_max_fib = 0;
int* baza = NULL;
void DEBUG(){cout << "DUPA\n"; cout.flush();}
int main()
{
	int t;
	cin >> t;
	for(int i = 0; i<t; i++)
		cin >> dana[i];

	for(int i = 0; i<t; i++)
		if(dana[i]>maksymalna) maksymalna = dana[i];
	
	for(int i = 0; i<45; i++)
		if(tab_fib[i]<maksymalna) id_max_fib = i;
	
	baza = new int[id_max_fib*id_max_fib];
	
	for(int a = 0; a<id_max_fib; a++)
	{
		for(int b = 0; b<id_max_fib; b++)
		{
			baza[a*id_max_fib + b] = tab_fib[a]*tab_fib[b];
		}
	}
	
	for(int a = 0; a<t; a++)
	{
		for(int i = 0; i < id_max_fib*id_max_fib; i++)
		{
			if(dana[a] == baza[i])
			{
				wynik[a] = true;
				break;
			}
		}
	}	
	for(int a = 0; a<t; a++)
	{
		if(wynik[a] == true) cout << "TAK" << endl;
		else cout << "NIE" << endl;
	}
	///////////////////////////////
	/*cout << "\n###########################\n\n";
	for(int i = 0; i<10; i++)
		cout << dana[i] << endl;
	cout << "max: " << maksymalna << endl;
	cout << "max_fib: " << tab_fib[id_max_fib] << endl;
	cout << "tab:" << id_max_fib*id_max_fib <<" \n" ;
	for (int i = 0; i < id_max_fib*id_max_fib; i++)
		cout << baza[i] << endl;*/
	return 0;
}