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
#include <iostream>
//#include "ilo.h" //this should be commented before sending as an answer and class declaration should be copied here, for tests purpose only
#include <cstdint>
#include <set>

using namespace std;

class Product{
	public:
		Product(uint32_t max);
		std::set<uint32_t> getFibonacciSequence();
		inline bool isFibonacci(uint32_t a);
		inline bool isFibonacciProduct(uint32_t a);
		static void run();
	protected:
		std::set<uint32_t> fib;
};

int main(){
	Product::run();
}

Product::Product(uint32_t max){
	uint32_t a=0;
	uint32_t b=1;
	uint32_t c=0;
	do{
		fib.insert(c);
		c=a+b;
		a=b;
		b=c;
	}while(c<=max);
}

std::set<uint32_t> Product::getFibonacciSequence(){
	return fib;
}

bool Product::isFibonacci(uint32_t a){
	return 1u==fib.count(a);
}

bool Product::isFibonacciProduct(uint32_t a){
	if(a==0)return true;
	for(uint32_t fibDivider : fib){
		if(fibDivider==0)continue;
		if((a%fibDivider)==0u){
			if(isFibonacci(a/fibDivider)) return true;
		}
	}
	return false;
}

void Product::run(){
	Product product(1000000000u);
	ios_base::sync_with_stdio(0);
	uint16_t t;
	uint32_t n;
	cin>>t;
	for(uint16_t i=0;i<t;++i){
		cin>>n;
		if(product.isFibonacciProduct(n)){
			cout<<"TAK\n";
		}
		else cout<<"NIE\n";
	}
}