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
83
/* Chcemy sprawdzić, czy podaną liczbę całkowitą można zapisać jako iloczyn dwóch liczb Fibonacciego.
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą t (1 - 10), oznaczającą liczbę przypadków testowych
do rozważenia. Dalej następuje t wierszy; i-ty z nich zawiera jedną liczbę całkowitą ni (0 - 10^9).
Twój program powinien wypisać na wyjście dokładnie t wierszy. W i-tym z tych wierszy powinno znaleźć
się jedno słowo TAK lub NIE, w zależności od tego, czy liczbę ni można przedstawić jako iloczyn dwóch liczb
Fibonacciego.

5	<t>
5	TAK
4	TAK
12	NIE
11	NIE
10	TAK
*/

#include <iostream>
#include <cmath>
using namespace std;

bool isSquare(int number) {
	int s = sqrt(number);
	return (s*s == number);
}

bool isFibonacci(int number) {
	return isSquare(5*number*number + 4) || isSquare(5*number*number - 4);
}

int main() {
	int cases = 0, max = 0;
	cin >> cases;
	int numCase[cases];

	for (int i = 0; i < cases; i++) {
		numCase[i] = 0;
		cin >> numCase[i];
		if (numCase[i] > max) max = numCase[i];
	}

	int fib[45];
	fib[0] = 0;
	fib[1] = 1;
	for (int i = 2; i < 45; i++) fib[i] = fib[i-1] + fib[i-2];

	// Okay, we've got everything we need. Process cases:
	for (int i = 0; i < cases; i++) {
		// Sanity check. Is this case a Fibonacci number?
		// If so, there's always 1 and this case.
		if (isFibonacci(numCase[i])) cout << "TAK" << endl;
		else {
			// Well, it couldn't be that easy.
			bool found = false;

			// The highest number here has about 1.5k divisors.
			// 48 divisors, filtered by fib[], should be enough.
			int divisor[48];
			int actualDivisors = 0;
			for (int j = 1; j < 45; j++) {
				if (numCase[i] % fib[j] == 0) {
					divisor[actualDivisors] = fib[j];
					actualDivisors++;
					if (fib[j] > numCase[i]) break;
				}
			}

			// Fine. Now, we've got all Fibonacci divisors here.
			// Let's bruteforce them. c:
			for (int j = 0; j < actualDivisors; j++) {
				for (int k = j; k < actualDivisors; k++) {
					if (divisor[k] * divisor[j] == numCase[i]) {
						found = true;
						break;
					}
				}

				if (found) break;
			}

			if (found) cout << "TAK" << endl;
			else cout << "NIE" << endl;
		}
	}
}