Description

斐波那契数列的定义为：k=0或1时，F[k]=k；k>1时，F[k]=F[k-1]+F[k-2]。数列的开头几项为0,1,1,2,3,5,8,13,21,34,55,…你的任务是判断给定的数字能否被表示成两个斐波那契数的乘积。

Input

第一行包含一个整数t(1<=t<=10)，表示询问数量。接下来t行，每行一个整数n_i(0<=n_i<=10^9)。

Output

输出共t行，第i行为TAK（是）或NIE（否），表示n_i能否被表示成两个斐波那契数的乘积。

Sample Input

5

5

4

12

11

10

Sample Output

TAK

TAK

NIE

NIE

TAK

HINT

 

Source

 

题解

这道题直接把1e9内的所有斐波那契数都推出来

每次读入的时候枚举斐波那契数，判断一下这个数是否能被整除，并且整除后的数是否在斐波那契数列中

1 #include
      
        2 using namespace std; 3 int T,n,num; 4 int fib[50]; 5 map
       
         flag; 6 int main(){ 7     scanf("%d",&T); 8     fib[1]=1; fib[2]=1; flag[1]=true; 9     for (int i=3;i<=45;i++) fib[i]=fib[i-1]+fib[i-2],flag[fib[i]]=true;10     while (T--){11         scanf("%d",&n);12         if (!n){13             puts("TAK");14             continue;15         }16         int t=1,d=sqrt(n);17         bool Flag=false;18         while (fib[t]<=d){19             if (!(n%fib[t])&&flag[n/fib[t]]){20                 Flag=true;21                 puts("TAK");22                 break;23             } 24             t++;25         }26         if (!Flag) puts("NIE");27     }28     return 0;29 }