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
#include<iostream>
#include<string>
#include<map>
#include<cmath>

using namespace std;


int main ()
{
  long int fib[50],liczby[10],max_fib,f0,f1,f2,liczba_sprawdzana,mozliwy_dzielnik;
  int k,l,m,t,max_fib_wsk;
  map<long int,int> fib_vect_flag;
  string odpowiedzi[10],odpowiedz;
  
  
  /* inicjalizuj zmienne, wczytaj t oraz dane wejsciowe */
  
   cin >> t;
   for(k=0;k<t;k++)
    cin >> liczby[k];
   
  /* wylicz i stablicuj wszystkie liczby Fibbonacciego < 10^9 */
   f0=0;f1=1;f2=0;max_fib=0;max_fib_wsk=1;fib[0]=f0;fib[1]=f1;
   fib_vect_flag [1]=1;
   do
    {f2=f0+f1;max_fib=f2;max_fib_wsk++;f0=f1;f1=f2;fib[max_fib_wsk]=f2;fib_vect_flag [f2]=1;}
    while(max_fib<1000000000);
    
  /* sprawdzenie - wypisz wyliczone liczby Fibbonacciego */
  
  /*
  for(k=0;k<=max_fib_wsk;k++)
   cout << fib[k] << endl;
  */
   
   
  /* dla testowych danych wejsciowych sprawdz, czy dana liczba moze byc iloczynem dwoch liczb Fibonacciego  */
  
  for(k=0;k<t;k++)
   {m=1;odpowiedz="NIE";liczba_sprawdzana=liczby[k];
    do
      {if(liczba_sprawdzana%fib[m]==0) 
         {mozliwy_dzielnik=liczba_sprawdzana/fib[m];if(fib_vect_flag.count(mozliwy_dzielnik)>0) odpowiedz="TAK";}
       m++;}
    while(fib[m]<sqrt(liczba_sprawdzana)+1);
    odpowiedzi[k]=odpowiedz;
    }      
    
                   
   for(k=0;k<t;k++)
    cout << odpowiedzi[k] << endl;
   
   
  /* cin >> t;*/
     
   
 return 0;   
 
}