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
#include <cstdio>
#include <cmath>


int binary_search(unsigned long *array,int first,int last, unsigned long search_key)
{
	int index;
  
  	if (first > last)
    	index = -1;
      	else
       	{
        	int mid = (first + last)/2;
	 
		if (search_key == array[mid])
			index = mid;
		else if (search_key < array[mid])
			index = binary_search(array,first, mid-1, search_key);
		else
			index = binary_search(array, mid+1, last, search_key);
		  
	} // end if
	return index;
}// end binarySearch

int main(void){
unsigned int t;
unsigned long fibos[] = {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 , 1134903170
};
int size = 46;


scanf("%u", &t); // Pobranie listy testów

for(int i = 0; i < t; i++){
unsigned long number;
scanf("%lu", &number);

if(binary_search(fibos, 0, size - 1, number)  != -1){
	printf("TAK\n");
}else{
	int j = 3;
	//printf("Numb = %lu\n", number);
	while(fibos[j] < number){
		double result = (double)number / (double)fibos[j];
		//printf("result = %lf\n", result);
		if((result - (int)result) == 0){
			//printf("Sprawdzam %d\n", (int)result);
			if(binary_search(fibos, 0, size - 1, (int)result) != - 1){
				printf("TAK\n");
				break;
			}
		}
		j++;
	}
	if(fibos[j] > number){
		printf("NIE\n");
	}	
	}
}
return 0;
}