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 #include #include // Helper definition #define VAR(v, i) __typeof(i) v=(i) #define FOR(i, j, k) for (int i = (j); i <= (k); ++i) #define FORD(i, j, k)for (int i=(j); i >= (k); --i) #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define REP(i, n) for(int i = 0;i <(n); ++i) #define SIZE_FIB 44 // last number 701 408 733 #define SIZE 10 #define T "TAK" #define F "NIE" /** Return array of Fibonacci sequence * @param n size sequence 1..n * @param tab array of next number of Fubonacci from tab[0] = f1, to tab[n-1] = fn */ void fib(int n,unsigned int tab[]) { tab[0] = 1; tab[1] = 1; FOR(i, 2, n - 1) { tab[i] = tab[i - 1] + tab[i - 2]; } } bool binary_search(unsigned int val, int begin,int end, unsigned int tab[]) { if (begin > end) return false; int div = (begin + end) / 2; if (tab[div] == val) return true; if (tab[div] < val) return binary_search(val, div + 1, end, tab); else return binary_search(val, begin, div - 1, tab); } int main(int argc, char **argv) { unsigned int fib_array[SIZE_FIB]; bool out; unsigned int ilo; int row; fib(SIZE_FIB, fib_array); scanf("%d", &row); REP(i, row) { out = false; scanf("%d", &ilo); FORD(j, SIZE_FIB - 1, 2) { if ( ilo % fib_array[j] == 0 && binary_search(ilo/fib_array[j], 0, SIZE_FIB, fib_array)) { out = true; break; } } if (out) printf("%s\n", T); else printf("%s\n", F); } return 0; }