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

using namespace std;

void mnozenie_kw(long long int a, long long int ** M1, long long int ** M2, long long int **MW, long long int modulo)
{
    long long int w;

    for(long long int i = 0; i < a; i++)
    {
        for(long long int j = 0; j < a; j++)
        {
            w = 0;
            for(long long int k = 0; k < a; k++)
                w += (M1[i][k] * M2[k][j]) % modulo;
            MW[i][j] = w % modulo;
        }
    }
}

void copy_mac_kw(long long int a, long long int ** M1, long long int ** M2)
{
    for(long long int i = 0; i < a; i++)
        for(long long int j = 0; j < a; j++)
            M2[i][j] = M1[i][j];
}

void podnies(long long int p, long long int a, long long int ** M, long long int modulo)
{
    long long int ** P, ** W;

    P = new long long int * [a];
    W = new long long int * [a];
    for(long long int i = 0; i < a; i++)
    {
        P[i] = new long long int[a];
        W[i] = new long long int[a];
    }

    for(long long int i = 0; i < a; i++)
    {
        for(long long int j = 0; j < a; j++)
            W[i][j] = 0;
        W[i][i] = 1;
    }

    while(p)
    {
        if (p & 1)
        {
            mnozenie_kw(a, W, M, P, modulo);
            copy_mac_kw(a, P, W);
        }
        p >>= 1;
        if(!p)
            break;

        mnozenie_kw(a, M, M, P, modulo);
        copy_mac_kw(a, P, M);
    }

    copy_mac_kw(a, W, M);
}

long long int fib(long long int n, long long int modulo)
{
    long long int ** J;//, F[2], P[2];
    J = new long long int * [2];
    J[0] = new long long int [2];
    J[1] = new long long int [2];

    J[0][0] = 1;
    J[0][1] = 1;
    J[1][0] = 1;
    J[1][1] = 0;

    podnies(n-1, 2, J, modulo);
    return J[0][0];

}

long long int dlugosc(long long int n)
{
    long long int r = n * log(1.618033)-log(sqrt(5))+1;
    if (r<=0)
        return 100;
    else
        return r;
}

int main()
{
    ios_base::sync_with_stdio(0);

    long long int n = 0, p;
    string s;
    cin >> s;
    int cyfr = s.length();

    n = atol(s.c_str());

    p = n;

    long long int period = 15 * (pow(10, cyfr));
    bool ok = false;
    do
    {
        p = fib(period, pow(10, cyfr));
        if(p == n)
            ok = true;

        period--;
    }while(period > 0 && dlugosc(period) >= (cyfr) && !ok);

    if(ok)
        cout << period+1;
    else
        cout << "NIE";


   return 0;
}