#include<bits/stdc++.h> using namespace std; typedef unsigned long long int64; int64 MOD; int64 x, x_size; int64 A, B, C, D, a, b, c, d, u, i, o, p, j; vector<int64> v[20]; int64 wczytaj(){ string a; cin >> a; x_size = a.size(); int64 y = 0; for( j = 0; j<a.size(); j++ ){ y += a[j]-48; y *= 10; } y /= 10; return y; } int64 fib(int64 n){ n--; A = D = 1; B = C = 0; a = b = c = 1; d = 0; while( n ){ if( n%2==1 ){ u = A, i = B, o = C, p = D; A = ((u*a)%MOD+(i*c)%MOD)%MOD; B = ((u*b)%MOD+(i*d)%MOD)%MOD; C = ((o*d)%MOD+(u*c)%MOD)%MOD; D = ((p*d)%MOD+(i*c)%MOD)%MOD; } n /= 2; u = a, i = b, o = c, p = d; a = ((u*u)%MOD + (i*o)%MOD)%MOD; b = ((u*i)%MOD + (i*p)%MOD)%MOD; c = ((o*p)%MOD + (u*o)%MOD)%MOD; d = ((p*p)%MOD + (i*o)%MOD)%MOD; } return A; } void brut(){ int64 mod = 10; for( int j = 1; j<x_size; j++ ) mod *= 10; for( int j = 1; j<=1500; j++ ){ if( fib((int64)j)%mod==x ){ printf("%d\n", j); return; } } } void wzorcowka(){ for( int j = 1; j<60; j++ ) if( fib(j)%10==x%10 ) v[1].push_back(j); int64 A = 60, K = 300; int64 mod = 100; for( int j = 2; j<=x_size; j++ ){ for( int k = 0; k<v[j-1].size(); k++ ){ for( int l = 0; A*l+v[j-1][k]<K; l++ ){ //if( j==2 )printf("%llu %llu %llu\n", fib(A*l+v[j-1][k]), mod, x); if( fib(A*l+v[j-1][k])%mod==x%mod ){ //printf("2"); v[j].push_back(A*l+v[j-1][k]); } } } if( A==60 )A=300; else if( A==300 )A=1500; else A*=10; if( K==300 )K=1500; else K*=10; mod*=10; } if( v[x_size].size()==0 ) printf("NIE\n"); else printf("15000000000000000000000000%llu\n", v[x_size][0]); /*for( int i = 0; i<=x_size; i++ ){ for( int j = 0; j<v[i].size(); j++ ) printf("%llu ", v[i][j]); printf("\n"); }*/ }; int main() { x = wczytaj(); MOD=10; for( int i = 0; i<x_size; i++ ) MOD*=10; wzorcowka(); return 0; }
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<bits/stdc++.h> using namespace std; typedef unsigned long long int64; int64 MOD; int64 x, x_size; int64 A, B, C, D, a, b, c, d, u, i, o, p, j; vector<int64> v[20]; int64 wczytaj(){ string a; cin >> a; x_size = a.size(); int64 y = 0; for( j = 0; j<a.size(); j++ ){ y += a[j]-48; y *= 10; } y /= 10; return y; } int64 fib(int64 n){ n--; A = D = 1; B = C = 0; a = b = c = 1; d = 0; while( n ){ if( n%2==1 ){ u = A, i = B, o = C, p = D; A = ((u*a)%MOD+(i*c)%MOD)%MOD; B = ((u*b)%MOD+(i*d)%MOD)%MOD; C = ((o*d)%MOD+(u*c)%MOD)%MOD; D = ((p*d)%MOD+(i*c)%MOD)%MOD; } n /= 2; u = a, i = b, o = c, p = d; a = ((u*u)%MOD + (i*o)%MOD)%MOD; b = ((u*i)%MOD + (i*p)%MOD)%MOD; c = ((o*p)%MOD + (u*o)%MOD)%MOD; d = ((p*p)%MOD + (i*o)%MOD)%MOD; } return A; } void brut(){ int64 mod = 10; for( int j = 1; j<x_size; j++ ) mod *= 10; for( int j = 1; j<=1500; j++ ){ if( fib((int64)j)%mod==x ){ printf("%d\n", j); return; } } } void wzorcowka(){ for( int j = 1; j<60; j++ ) if( fib(j)%10==x%10 ) v[1].push_back(j); int64 A = 60, K = 300; int64 mod = 100; for( int j = 2; j<=x_size; j++ ){ for( int k = 0; k<v[j-1].size(); k++ ){ for( int l = 0; A*l+v[j-1][k]<K; l++ ){ //if( j==2 )printf("%llu %llu %llu\n", fib(A*l+v[j-1][k]), mod, x); if( fib(A*l+v[j-1][k])%mod==x%mod ){ //printf("2"); v[j].push_back(A*l+v[j-1][k]); } } } if( A==60 )A=300; else if( A==300 )A=1500; else A*=10; if( K==300 )K=1500; else K*=10; mod*=10; } if( v[x_size].size()==0 ) printf("NIE\n"); else printf("15000000000000000000000000%llu\n", v[x_size][0]); /*for( int i = 0; i<=x_size; i++ ){ for( int j = 0; j<v[i].size(); j++ ) printf("%llu ", v[i][j]); printf("\n"); }*/ }; int main() { x = wczytaj(); MOD=10; for( int i = 0; i<x_size; i++ ) MOD*=10; wzorcowka(); return 0; } |