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
#include <stdio.h>
#include <string.h>

int main()
{
  unsigned fibs[ 100 ];
  unsigned num = 0;
  bool notFound = true;
  int tests = 0;
  int j = 0;
  int k = 0;
  unsigned tmp = 0;
  
  memset( fibs, 0, 100 * sizeof(unsigned) );
  fibs[ 1 ] = 1;

  scanf("%u", &tests);

  for(int i = 0; i < tests; ++i)
  {
    scanf("%u", &num);
    if( num < 2 )
    {
      printf("TAK\n");
    } 
    else
    {
      j = 2;
      notFound = true;
      do
      {
        if( fibs[ j ] == 0 )
          fibs[ j ] = fibs[ j - 1 ] + fibs[ j - 2 ];

        if( !( num % fibs[ j ] ) )
        {
          k = 2;
          tmp = num / fibs[ j ];
          do
          {
            if( fibs[ k ] == 0 )
              fibs[ k ] = fibs[ k - 1 ] + fibs[ k - 2 ];
            k++;
          }while( fibs[ k ] <= tmp );
          if( fibs[ k - 1 ] == tmp )
          {
            printf("TAK\n");
            notFound = false;
          }; 
        };
        j++;
      }while( ( j < 100 ) && ( fibs[ j ] <= num ) && notFound );
      if( notFound )
        printf("NIE\n");
    };
  };
  return 0;
};