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
//Łukasz Proksa
//Silesian University of Technology, Poland
//Contest:	Potyczki Algorytmiczne 2014
//Task:		Iloczyn (trial)
//Solved!	O(44*t)
#include <cstdio>
#include <math.h>
using namespace std;

#define FOR(i, p, k) for(int i = (p); i < (k); i++)
const int MAX_N = 1000000000; //10^9

int t, n;
int fib[23]; //22 liczby

void init();

bool daSie(int n) {
	int i = 0;
	int j = 21;
	int sq = floor(sqrt(n));
	//printf("%d\n",sq);
	while(fib[i] <= sq && i < 22) { //amortyzowany koszt O(2*22)
		//printf("sprawdzam %d\n", fib[i]);
		if(n % fib[i] == 0) { //fib[i] dzieli
			int r = n / fib[i];
			//printf("dzieli, czy dzielnik %d jest fib? ", r);
			while(fib[j] > r) { //r >= 1
				//printf("fib[j]: %d\n", fib[j]);
				j--;
			}
			if(fib[j] == r) { //czy dzielnik jest fib
				//printf("tak\n");
				return true;
			}
			//printf("nie\n");
		}
		i++;
	}
	return false;
}

int main() {
	init();
	//printf("%d %d %d %d\n", fib[0], fib[43], fib[1], fib[5]);
	scanf("%d", &t);
	FOR(i, 0, t) {
		scanf("%d", &n);
		if(daSie(n)) printf("TAK\n");
		else printf("NIE\n");
	}
	return 0;
}

void init() {
	fib[0]=1; fib[1]=2; fib[2]=3; fib[3]=5; fib[4]=8; 
	fib[5]=13; fib[6]=21; fib[7]=34; fib[8]=55; fib[9]=89; 
	fib[10]=144; fib[11]=233; fib[12]=377; fib[13]=610; fib[14]=987; 
	fib[15]=1597; fib[16]=2584; fib[17]=4181; fib[18]=6765; fib[19]=10946; 
	fib[20]=17711; fib[21]=28657;
}