#include<bits/stdc++.h> #define PII pair<int,int> #define f first #define s second #define VI vector<int> #define LL long long #define MP make_pair #define LD long double #define PB push_back #define ALL(V) V.begin(),V.end() #define abs(x) max((x),-(x)) #define PDD pair<LD,LD> #define VPII vector< PII > #define siz(V) ((int)V.size()) #define FOR(x, b, e) for(int x=b;x<=(e);x++) #define FORD(x, b, e) for(int x=b;x>=(e);x--) #define REP(x, n) for(int x=0;x<(n);x++) #define mini(a,b) a=min(a,b) #define maxi(a,b) a=max(a,b) using namespace std; char in[20]; LL MOD=1; unordered_map<LL,LL> M; LL mul(LL a,LL b, LL m=MOD) //a*b mod m { LL q=(LL)((LD)a*(LD)b/(LD)m); LL r=a*b-q*m; // ma się przekręcać return (r%m+m)%m; } LL kwa(LL a,LL m=MOD) { return mul(a,a,m); } LL fib(LL x) { if(M.count(x))return M[x]; if(x%2==1) { return M[x]=(kwa(fib(x/2)) + kwa(fib(x/2+1)))%MOD; } else { return M[x]=(mul(2*fib(x/2-1)+fib(x/2), fib(x/2))); } } void init() { M[0]=0; M[1]=1; M[2]=1; } const int MXX=250; //chyba wystarczy 200 void solve() { M.clear(); init(); MOD=1; scanf("%s",in); int n=strlen(in); LL value; sscanf(in,"%lld",&value); REP(i,n)MOD*=10; maxi(n,4); LL skok=1; LL k=50; LL modt=10000; mini(modt,MOD); FOR(i,4,n) { int zlicz=0; while(fib(k)%modt!=value%modt) { zlicz++; if((i==4&&zlicz>15500)||(i>4&&zlicz>MXX)) { puts("NIE"); return; } k+=skok; } skok=modt+modt/2; skok/=20; modt*=10; } /* if(fib(k)%MOD!=value) { puts("DUUUUUUUUUUUUUUPAAAAAA111"); return; } */ // cerr<<"M.size(): "<<M.size()<<endl; // cerr<<in<<": ";puts("TAK");return; // cerr<<fib(k)<<endl; printf("%lld\n",k); } main() { solve(); }
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 | #include<bits/stdc++.h> #define PII pair<int,int> #define f first #define s second #define VI vector<int> #define LL long long #define MP make_pair #define LD long double #define PB push_back #define ALL(V) V.begin(),V.end() #define abs(x) max((x),-(x)) #define PDD pair<LD,LD> #define VPII vector< PII > #define siz(V) ((int)V.size()) #define FOR(x, b, e) for(int x=b;x<=(e);x++) #define FORD(x, b, e) for(int x=b;x>=(e);x--) #define REP(x, n) for(int x=0;x<(n);x++) #define mini(a,b) a=min(a,b) #define maxi(a,b) a=max(a,b) using namespace std; char in[20]; LL MOD=1; unordered_map<LL,LL> M; LL mul(LL a,LL b, LL m=MOD) //a*b mod m { LL q=(LL)((LD)a*(LD)b/(LD)m); LL r=a*b-q*m; // ma się przekręcać return (r%m+m)%m; } LL kwa(LL a,LL m=MOD) { return mul(a,a,m); } LL fib(LL x) { if(M.count(x))return M[x]; if(x%2==1) { return M[x]=(kwa(fib(x/2)) + kwa(fib(x/2+1)))%MOD; } else { return M[x]=(mul(2*fib(x/2-1)+fib(x/2), fib(x/2))); } } void init() { M[0]=0; M[1]=1; M[2]=1; } const int MXX=250; //chyba wystarczy 200 void solve() { M.clear(); init(); MOD=1; scanf("%s",in); int n=strlen(in); LL value; sscanf(in,"%lld",&value); REP(i,n)MOD*=10; maxi(n,4); LL skok=1; LL k=50; LL modt=10000; mini(modt,MOD); FOR(i,4,n) { int zlicz=0; while(fib(k)%modt!=value%modt) { zlicz++; if((i==4&&zlicz>15500)||(i>4&&zlicz>MXX)) { puts("NIE"); return; } k+=skok; } skok=modt+modt/2; skok/=20; modt*=10; } /* if(fib(k)%MOD!=value) { puts("DUUUUUUUUUUUUUUPAAAAAA111"); return; } */ // cerr<<"M.size(): "<<M.size()<<endl; // cerr<<in<<": ";puts("TAK");return; // cerr<<fib(k)<<endl; printf("%lld\n",k); } main() { solve(); } |