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
#include <cstdio>
#include <utility>
#include <cstring>
#include <queue>
using namespace std;

typedef long long ll;
ll mod;

struct matrix
{
    ll a, b, c, d;
    matrix(ll A = 0, ll B = 0, ll C = 0, ll D = 0): a(A % mod), b(B % mod), c(C % mod), d(D % mod) { }
};

ll mult(ll a, ll b)
{
    if(b == 0) return 0;
    if(b & 1) return (a + mult((a + a) % mod, b / 2)) % mod;
    return mult((a + a) % mod, b / 2);
}

matrix operator*(matrix a, matrix b)
{
    return matrix(mult(a.a, b.a) + mult(a.b, b.c), mult(a.a, b.b) + mult(a.b, b.d),
		  mult(a.c, b.a) + mult(a.d, b.c), mult(a.c, b.b) + mult(a.d, b.d));
}

matrix operator^(matrix a, ll b)
{
    if(b == 1) return a;
    if(b & 1) return a * (a ^ (b - 1));
    return (a * a) ^ (b / 2);
}

ll pow10(int k)
{
    ll ans = 1;
    while(k--)
	ans *= 10;
    return ans;
}

inline ll fib(ll k)
{
    return k == 0 ? 0 : (matrix(1, 1, 1, 0) ^ k).c;
}

int main()
{
    ll c;
    char s[20];
    scanf("%s", s);
    int n = strlen(s);
    sscanf(s, "%lld", &c);
    queue<pair<ll, int> > q;
    pair<ll, ll> p(1, 0);
    mod = pow10(min(3, n));
    for(int i = 0; i < 1500; i++)
    {
	if(p.second == c % mod) q.push(make_pair((ll)i, 3));
	p = make_pair((p.first + p.second) % mod, p.first);
    }
    while(!q.empty())
    {
	auto f = q.front();
	q.pop();
	if(f.second >= n)
	{
	    printf("%lld\n", f.first + (ll)1.5e18);
	    return 0;
	}
	else
	{
	    mod = pow10(f.second + 1);
	    for(int i = 0; i < 10; i++)
		if(fib(f.first + mod / 20 * 3 * i) == c % mod)
		    q.push(make_pair(f.first + mod / 20 * 3 * i, f.second + 1));
	}
    }
    puts("NIE");
}