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

int main()
{
    uint64_t a=0, b=1;
    uint64_t fk=a+b;
    uint64_t k=2;

    uint64_t c;
    std::cin >> c;

    if( c == 0 || c == 1 )
    {
        std::cout << c << std::endl;
        return 0;
    }
    if( c == 2 || c == 3 )
    {
        std::cout << c+1 << std::endl;
        return 0;
    }
    uint64_t t=10;
    uint64_t w = 1;// t = 10^w
    while( c/t >= 1)
    {   
        ++w;
        t *= 10;
    }
    
    uint64_t xk = 1, xk1 = 1, x2k = 1, x2k1 = 2;
    k = 1;
    while( x2k1 < c )
    {
        xk = x2k;
        xk1 = x2k1;
        x2k = xk*(2*xk1-xk);
        x2k1 = xk1*xk1 + xk*xk;
        k *= 2;
    }

    uint64_t max_k = t/10*15;

    a = xk;
    b = xk1;
    fk = a+b;
    k += 2;

    bool found = false;
    while( ( fmod( fk, t ) != c ) && ( k<max_k ) )
    {
        a = b; 
        b = fk;
        fk = fmod(a+b, t );
        ++k; 
    }

    if( ( fmod( fk, t ) != c ) || (k==max_k))
    {
        std::cout << "NIE" << std::endl;
    }
    else
    {
        std::cout << k << std::endl;
    }

    return 0;
}