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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const unsigned long long MILION = 1000000;
const unsigned long long MAXNN = MILION * MILION * MILION;

void potega_macierzy_modulo(unsigned long long n, unsigned long long* t, unsigned long long a, unsigned long long b, unsigned long long m) {
    unsigned long long p1,p2;
    if(n>=1) {
        potega_macierzy_modulo(n/2, t, a, b, m);
        p1=t[0]+t[3];
        p2=t[2];
        t[0]=t[0]*t[0]+t[1]*t[2];
        t[2]*=p1;
        t[3]=t[3]*t[3]+t[1]*p2;
        t[1]*=p1;
        if(n%2) {
            p1=t[0];
            t[0]=t[2];
            t[2]=t[2]*b+p1*a;
            p1=t[1];
            t[1]=t[3];
            t[3]=t[3]*b+p1*a;
        }
        t[0]%=m;
        t[1]%=m;
        t[2]%=m;
        t[3]%=m;
    } else {
        t[0]=1;
        t[1]=0;
        t[2]=0;
        t[3]=1;
    }
}

unsigned long long fib(unsigned long long n, unsigned long long m) {
    unsigned long long t[4];
    unsigned long long a,b,x,y,res;
    a = 1;
    b = 1;
    x = 1;
    y = 1;
    if (n==0)
        return 0;
    if (n==1)
        return 1;
    potega_macierzy_modulo(n-3, t, a, b, m);
    return (x*(a*t[0]+b*t[2])+y*(a*t[1]+b*t[3])) % m;
}



bool sprawdz(unsigned long long f, unsigned long long a,  long long iter) {
    unsigned long long ff = fib(f, MAXNN);
    unsigned long long md = 1;
    iter--;
    while (iter--)
        md *= 10;
    //prunsigned long longf("sprawdz: %llu %llu %llu %llu %llu\n", f, ff, a, iter, md);
    return ((ff / md) % 10 == a);
}

char t[107];
int main() {
    for (unsigned long long i = 0; i < 100; i++)
        printf("%llu\n", fib(i, MAXNN));
    cin>>t;
    unsigned long long l;
    for (unsigned long long j = 0; j < 20; j++) {
        if (t[j] != 0) {
            t[j] = t[j] - '0';
        } else {
            l = j;
            j = 20;
        }
    }
    unsigned long long s = 60;
    unsigned long long p[107], pNowe[107];
    unsigned long long krok = 1;
    unsigned long long ile = 1;
    p[0] = 1;
    long long iter = 0;
    while (l > 0) {
        l--;
        iter++;
        unsigned long long ileNowe = 0;
        unsigned long long a = t[l];
        //prunsigned long longf("%d %d %d\n", t[0], t[1], t[2]);
        for (unsigned long long i = 0; i < ile; i++) {
            if (i == 0 || p[i - 1] != p[i]) {
                unsigned long long f = p[i];
                while (f < s) {
                    if (sprawdz(f, a, iter)) {
                        if (l == 0) {
                            printf("%llu\n", f);
                            return 0;
                        }
                        pNowe[ileNowe] = f;
                        ileNowe++;
                    }
                    f += krok;
                }
            }
        }
        for (unsigned long long i = 0; i < ileNowe; i++)
            p[i] = pNowe[i];
        sort(p, p + ileNowe);
        ile = ileNowe;
        krok = s;
        if (iter < 3)
            s *= 5;
        else
            s *= 10;
    }
    printf("NIE\n");
}