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
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#ifndef DEBUG_MODE
#define NDEBUG
#endif

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;
typedef unsigned long long ull;

ull mul(ull a, ull b, ull mod) {
	ull result;
	if(b == 0)
		return 0LL;
	result = mul(a, b >> 1, mod);
	result = (result + result) % mod;
	if(b & 1)
		result = (result + a) % mod;
	return result;
}

void mul(ull f[2][2], ull m[2][2], ull mod) {
	ull x = (mul(f[0][0], m[0][0], mod) + mul(f[0][1], m[1][0], mod)) % mod;
	ull y = (mul(f[0][0], m[0][1], mod) + mul(f[0][1], m[1][1], mod)) % mod;
	ull z = (mul(f[1][0], m[0][0], mod) + mul(f[1][1], m[1][0], mod)) % mod;
	ull w = (mul(f[1][0], m[0][1], mod) + mul(f[1][1], m[1][1], mod)) % mod;

	f[0][0] = x;
	f[0][1] = y;
	f[1][0] = z;
	f[1][1] = w;
}

void power(ull f[2][2], ull n, ull mod) {
	if(n == 0 || n == 1)
		return;
	ull m[2][2] = {{1, 1}, {1, 0}};

	power(f, n / 2, mod);
	mul(f, f, mod);

	if(n % 2 != 0)
		mul(f, m, mod);
}

// Even better: http://codeforces.com/blog/entry/14516
ull fib(ull n, ull mod) {
	ull f[2][2] = {{1, 1}, {1, 0}};
	if(n == 0)
		return 0;
	power(f, n - 1, mod);
	return f[0][0];
}

typedef vector<pair<ull, ull>> FibPairs;

ull modCycle(ull mod) { return mod == 10 ? 60 : mod == 100 ? 300 : mod + mod / 2; }

FibPairs computeAll(ull mod, ull value) {
	ull a = 0, b = 1;

	ull max_count = modCycle(mod);
	ull val_mod = value % mod;

	FibPairs out;

	if(val_mod == 0)
		out.push_back(make_pair(0ll, 0ll));
	if(val_mod == 1)
		out.push_back(make_pair(1ll, 1ll));

	for(int k = 0; k < max_count; k++) {
		ull next = (a + b) % mod;
		a = b;
		b = next;
		if(next == val_mod)
			out.push_back(make_pair(k + 2, next));
	}

	return out;
}

int main() {
	string svalue;
	cin >> svalue;
	if(svalue.empty())
		return false;

	ull target_mod = 1, value;
	for(int n = 0; n < (int)svalue.size(); n++)
		target_mod *= 10;
	sscanf(svalue.c_str(), "%llu", &value);

	ull mod = 10;
	FibPairs vals = computeAll(mod, value);

#ifdef DEBUG_MODE
	printf("Value: %llu  mod: %llu\n", value, target_mod);
#endif

	while(mod < target_mod) {
#ifdef DEBUG_MODE
		printf("Step: %lld -> %lld\n", mod, mod * 10);
#endif
		FibPairs new_vals;
		ull next_mod = mod * 10;
		ull cur_cycle = modCycle(mod), next_cycle = modCycle(next_mod);
		ull steps = next_cycle / cur_cycle;
		ull val_mod = value % next_mod;

		for(int n = 0; n < (int)vals.size(); n++) {
#ifdef DEBUG_MODE
			printf("%lld: %lld\n", vals[n].first, vals[n].second);
#endif
			ull k = vals[n].first;
			for(ull i = 0; i < steps; i++) {
				ull k = vals[n].first + cur_cycle * i;
				ull f = fib(k, next_mod);
				if(f == val_mod) {
					new_vals.push_back(make_pair(k, f));
				}
			}
		}
#ifdef DEBUG_MODE
		printf("\n");
#endif

		vals.swap(new_vals);
		mod = next_mod;
	}

	if(vals.empty())
		cout << "NIE" << endl;
	else {
		std::sort(vals.begin(), vals.end());
		cout << vals.front().first << endl;
	}

	return 0;
}