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
#include<iostream>
#include<cmath>
using namespace std;
long int fib[50];
main()
{
    fib[0]=0;
    fib[1]=1;
    for(int i=2; i<47; i++) fib[i]=fib[i-1]+fib[i-2];
    int t, n;
    cin>>t;
    while(t--){
                cin>>n;
                bool czy=false;
                for(int i=1; fib[i]<=n; i++){
                                    if(n%fib[i]==0){
                                                    int l=1, p=46;
                                                    int il=n/fib[i];
                                                    while(l<=p){
                                                            int s=(l+p)/2;
                                                            if(fib[s]==il){
                                                                            czy=true;
                                                                            break;
                                                                            }
                                                            if(fib[s]>il) p=s-1;
                                                            else l=s+1;
                                                        }
                                                    }
                                    if(czy) break;
                                }
                if(czy) cout<<"TAK"<<endl;
                else cout<<"NIE"<<endl;
            }
        }