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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <array>

constexpr uint64_t mynum[21] = {
1ULL, 
60ULL, 
300ULL, 
1500ULL, 
15000ULL, 
150000ULL, 
1500000ULL,
15000000ULL, 
150000000ULL,
1500000000ULL,
15000000000ULL,
150000000000ULL,
1500000000000ULL,
15000000000000ULL,
150000000000000ULL,
1500000000000000ULL, 
15000000000000000ULL,
150000000000000000ULL,
1500000000000000000ULL,
15000000000000000000ULL };
uint64_t szukana = 0, m = 1;

class matrix {
  public:
   std::array<uint64_t, 4> v;
   matrix operator*(const matrix& x) const {
     return  {(v[0] * x.v[0] + v[1] * x.v[2])%m,  (v[0] * x.v[1] + v[1] * x.v[3])%m,
              (v[2] * x.v[0]  + v[3]* x.v[2])%m,  (v[2] * x.v[1] + v[3] * x.v[3])%m};
    }
 };

matrix square(const matrix& x) {
  return x*x;
 }

matrix fast_pow(matrix x, uint64_t n) {
  if(n==0) {
    return {1, 0, 0, 1};
   }
  if(n%2 == 1) {
    return x * square(fast_pow(x, n/2));
   }
  return square(fast_pow(x, n/2));
 }

uint64_t fib(uint64_t i) {
  return fast_pow({1, 1, 1, 0}, i).v[1];
 }

uint64_t find(uint64_t i = 120, uint64_t temp_mod = 10, unsigned depth = 0) {
  //std::cerr << i << ": " << fib(i) << "~" <<szukana << '\n';
  if(fib(i) == szukana)
   return i;
  const uint64_t to_add = mynum[depth];
  for(unsigned t = 0; t < 150; ++t) {
    if(fib(i)%temp_mod == szukana%temp_mod) {
      const uint64_t answer = find(i, temp_mod * 10, depth + 1);
      if(answer != 0) {
        return answer;
       }
     }
    i += to_add;
   }
  return 0;
 }

int main() {
  std::string szukany;
  std::cin >> szukany;
  for(size_t i = 0; i < szukany.size(); ++i) {
    szukana += m * (szukany[szukany.size() - (1+i)]-'0');
    m *= 10;
   }
  const uint64_t answer = find();
  if(answer == 0) {
    std::cout << "NIE\n";
    return 0;
   }
  std::cout << answer << '\n';
 }