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

using namespace std;

typedef long long BigInt;

BigInt addmod( BigInt x, BigInt y, BigInt m )
{
  x %= m;
  y %= m;
  BigInt sum = x-m+y; // -m <= sum < m-1
  return sum < 0 ? sum + m : sum;
}

BigInt timesmod( BigInt x, BigInt y, BigInt m )
{
  x %= m;
  y %= m;
  BigInt a = x < y ? x : y; // min
  BigInt b = x < y ? y : x; // max
  BigInt product = 0;
  for (; a != 0; a >>= 1, b = addmod(b,b,m) )
    if (a&1) product = addmod(product,b,m);
  return product;
}

void multiply(unsigned long long int F[2][2], unsigned long long int M[2][2], unsigned long long int mod);

void power(unsigned long long int F[2][2], unsigned long long int n, unsigned long long int mod);

/* function that returns nth Fibonacci number */
unsigned long long int fib(unsigned long long int n, unsigned long long int mod)
{
	unsigned long long int F[2][2] = {{1,1},{1,0}};
  if (n == 0)
    return 0;
  power(F, n-1, mod);
  return F[0][0];
}

/* Optimized version of power() in method 4 */
void power(unsigned long long int F[2][2], unsigned long long int n, unsigned long long int mod)
{
  if( n == 0 || n == 1)
      return;
  unsigned long long int M[2][2] = {{1,1},{1,0}};

  power(F, n/2, mod);
  multiply(F, F, mod);

  if (n%2 != 0)
     multiply(F, M, mod);
}

void multiply(unsigned long long int F[2][2], unsigned long long int M[2][2], unsigned long long int mod)
{
	unsigned long long int x =  timesmod(F[0][0],M[0][0],mod) + timesmod(F[0][1], M[1][0], mod);
	unsigned long long int y =  timesmod(F[0][0],M[0][1],mod) + timesmod(F[0][1], M[1][1], mod);
	unsigned long long int z =  timesmod(F[1][0],M[0][0],mod) + timesmod(F[1][1] ,M[1][0], mod);
	unsigned long long int w =  timesmod(F[1][0],M[0][1],mod) + timesmod(F[1][1], M[1][1], mod);

  F[0][0] = x%mod;
  F[0][1] = y%mod;
  F[1][0] = z%mod;
  F[1][1] = w%mod;
}
/* Driver program to test above function */

unsigned long long int nastepny_przeskok(unsigned long long int p){
    if (p==1) return 60;
    if (p==300) return 1500;
    if (p==60) return 300;
    return p*10;
}

unsigned long long int czy_da_sie(unsigned long long int do_znalezienia,
                                  unsigned long long int do_dodania,
                                  unsigned long long int n,
                                  unsigned long long int przeskok,
                                  unsigned long long int modulo,
                                  unsigned long long int cel){

            if(fib(n, 1000000000000000000)*10    <modulo) return 0;
            if(modulo==cel) return n;
    do_znalezienia+=(do_dodania%10)*modulo;
    modulo*=10;
    do_dodania-=do_dodania%10;
    do_dodania/=10;
    unsigned long long int zakres = nastepny_przeskok(przeskok)/przeskok *2;
    unsigned long long int wynik;
    for(unsigned int i=0; i <= zakres ; i++){
        if(fib(n, modulo)==do_znalezienia){
            //cout << "znaleziono " << fib(n, modulo) << " " << do_znalezienia<< " " << n << endl;
            //getch();
            wynik=czy_da_sie( do_znalezienia, do_dodania, n, nastepny_przeskok(przeskok), modulo, cel);
            if(wynik) return wynik;
        }
        n+=przeskok;
    }
    return 0;
}

int main()
{
    unsigned long long int c, wynik, cel;
    string s;
    cel=1;
    cin >> s;
    c=s.length();
    while(c--) cel*=10;
    c=atoll(s.c_str());

    wynik=czy_da_sie(0, c, 1, 1, 1, cel);
    if(wynik) cout << wynik;
    else cout << "NIE";
    return 0;
}