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
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;
typedef unsigned long long int LL;

const LL threshold = 100000000;

LL mulmod(LL a, LL b, LL m) {
   if(a<threshold && b<threshold) return (a*b)%m;
   LL res = 0;
   while (a != 0) {
      if (a & 1) res = (res + b) % m;
      a >>= 1;
      b = (b << 1) % m;
   }
   return res;
}

LL fastFib(LL n, LL mod){
   if(n==0) return 0;
   if(n<=2) return 1;
   LL k=n/2;
   LL Fk = fastFib(k,mod);
   LL Fk1 = fastFib(k+1,mod);
   //printf("%llu->%llu,%llu->%llu\n",k,Fk,k+1,Fk1);
   if(n%2==0){
      //n=2k
      LL a = mulmod(Fk1,2,mod)%mod;
      LL b = Fk;
      return mulmod(Fk,(mod+a-b)%mod,mod)%mod;
   }else{
      //n=2k+1
      LL a =mulmod(Fk1,Fk1,mod)%mod;
      LL b =mulmod(Fk,Fk,mod)%mod;
      return (a+b)%mod;
   }
}

LL cycle(LL n){
   if(n==1) return 60;
   if(n==2) return 300;
   LL c = 15;
   for(int i=1;i<n;++i) c*=10;
   return c;
}

int main(){
   //for(int i=0;i<10;i++) printf("F%d == %llu\n",i,fastFib(i,10));
   char zapis[20];
   scanf("%s",zapis);
   LL n = strlen(zapis);
   LL liczba=0;
   for(size_t i=0;i<n;++i){
      liczba*=10;
      liczba+=zapis[i]-'0';
   }
   //printf("%llu mod 10^%llu\n",liczba,n);
   vector<LL> current,next;
   //initialize for first digit
   if(liczba%10==0) current.push_back(0);
   if(liczba%10==1) current.push_back(1);
   LL fa=0,fb=1;
   for(LL i=2;i<60;++i){
      LL fc = (fa+fb)%10;
      fa=fb;
      fb=fc;//FIB
      if(liczba%10==fc){
         current.push_back(i);
      }
   }
   //we got all possible 60k+i
   LL modulo=10;
   for(size_t i=2;i<=n;++i){//now we go with higher powers of ten
      modulo*=10;//current modulo
      next.clear();
      LL currentOrder = cycle(i-1);
      LL nextOrder = cycle(i);
      for(size_t j=0;j<current.size();++j){//let's check all candidates
         for(LL f=current[j]%currentOrder;f<nextOrder;f+=currentOrder){
            LL fib = fastFib(f,modulo);
            //printf("Checking F%llu = %llu (mod %llu)\n",f,fib,modulo);
            if(fib==liczba%modulo){
               next.push_back(f);//advance matched
               //printf("%llu is %llu\n",f,fib);
            }
         }
      }
      //printf("%d mod %llu(10^%d+1)\n",next.size(),modulo,i);
      current = next;
   }
   if(current.empty()){
      puts("NIE");
   }else{
      LL smallest = current[0];
      //for(size_t i=1;i<current.size();++i) if(current[i]<smallest) smallest=current[i];
      printf("%llu\n",smallest);
   }
   //for(int i=1;i<=5;++i) printf("C(%d)=%llu\n",i,cycle(i));
}