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
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <cmath>
#include <set>

using namespace std;

vector<unsigned> generuj_liczby_Fibonacciego(const unsigned);
inline bool sprawdz(const unsigned, const set<unsigned>&);

int main(void) {
  ios_base::sync_with_stdio(false);
  unsigned n;
  cin >> n;
  vector<unsigned> szukane; szukane.reserve(n);
  copy(istream_iterator<unsigned>(cin), istream_iterator<unsigned>(),
       back_inserter(szukane));
  const unsigned najwieksza = *max_element(begin(szukane), end(szukane));
  const vector<unsigned> temp_liczby_Fibonacciego = generuj_liczby_Fibonacciego(najwieksza);
  const set<unsigned> liczby_Fibonacciego(begin(temp_liczby_Fibonacciego), end(temp_liczby_Fibonacciego));
  auto& odpowiedzi = szukane;
  transform(begin(szukane), end(szukane), begin(odpowiedzi),
            [=](const unsigned x) {return sprawdz(x, liczby_Fibonacciego) ? 1U : 0U;});
  transform(begin(odpowiedzi), end(odpowiedzi), ostream_iterator<string>(cout,"\n"),
            [](const unsigned x){return x==1? "TAK" : "NIE";});
 }

inline unsigned kolejna(void) {
  static unsigned a = 1, b = 1;
  unsigned c = a + b;
  a = b;
  b = c;
  return c;
 }

vector<unsigned> generuj_liczby_Fibonacciego(const unsigned najwieksza) {
  vector<unsigned> liczby_Fibonacciego = {1};
  while(liczby_Fibonacciego.back() < najwieksza) {
    liczby_Fibonacciego.push_back(kolejna());
   }
  return liczby_Fibonacciego;
 }

inline bool sprawdz(const unsigned sprawdzana, const set<unsigned>& liczby_Fibonacciego) {
  if(sprawdzana == 0)
   return true;
  for(const auto& x : liczby_Fibonacciego)
   if(sprawdzana % x == 0 && liczby_Fibonacciego.count(sprawdzana/x))
    return true;
  return false;
 }