#include <cstdio> #include <cstring> #include <vector> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define FOR(a,b,c) for(int a=(b);a<=(c);a++) typedef long long ll; struct macierz{ macierz(ll a=0, ll b=0, ll c=0, ll d=0) { t[0][0] = a; t[0][1] = b; t[1][0] = c; t[1][1] = d; } ll t[2][2]; }; struct wektor{ wektor(ll a=0, ll b=0) { t[0] = a; t[1] = b; } ll t[2]; bool operator== (wektor const& a) { return a.t[0] == t[0] && a.t[1] == t[1]; } bool operator!= (wektor const& a) { return !(*this == a); } }; ll mnoz(ll a, ll b, ll mod) { ll res = 0; while (b) { if (b&1) res = res + a; if (res >= mod) res -= mod; a = a + a; if (a >= mod) a -= mod; b /= 2; } return res; } macierz zero() { return macierz(); } macierz jeden() { return macierz(1, 0, 0, 1); } macierz mnoz(macierz const& a, macierz const& b, ll mod) { macierz res = macierz(); REP(i,2) REP(j,2) REP(k,2) res.t[i][k] += mnoz(a.t[i][j], b.t[j][k], mod); REP(i,2) REP(j,2) res.t[i][j] %= mod; return res; } macierz pot(macierz a, ll b, ll mod) { macierz res = jeden(); while (b) { if (b&1) res = mnoz(res, a, mod); a = mnoz(a, a, mod); b /= 2; } return res; } wektor mnoz(macierz const& a, wektor const& b, ll mod) { wektor res = wektor(); REP(i,2) REP(j,2) res.t[i] += mnoz(a.t[i][j], b.t[j], mod); REP(i,2) res.t[i] %= mod; return res; } wektor wfib() { return wektor(0, 1); } macierz mfib() { return macierz(1, 1, 1, 0); } /*void wylicz() { wektor start = fib(); wektor fibw = start; ll mod = 1; ll okres = 1; FOR(i,1,18) { mod *= 10; macierz fibm = pot(fib(), okres, mod); int cnt = 1; fibw = mnoz(fibm, fibw, mod); while (fibw != start) { ++cnt; fibw = mnoz(fibm, fibw, mod); } okres *= cnt; printf("%lldLL,",okres); } }*/ ll okres[19] = {1,60LL,300LL,1500LL,15000LL,150000LL,1500000LL,15000000LL,150000000LL,1500000000LL,15000000000LL,150000000000LL,1500000000000LL,15000000000000LL,150000000000000LL,1500000000000000LL,15000000000000000LL,150000000000000000LL,1500000000000000000LL}; int main() { char cyf[100]; scanf("%s",cyf); int n = strlen(cyf); ll mod = 1; vector<ll> pom, potencjalni = {0}; FOR(i,1,n) { mod *= 10; int cyfra = cyf[n-i] - '0'; ll ilosc = okres[i] / okres[i-1]; macierz m = pot(mfib(), okres[i-1], mod); for (ll poz: potencjalni) { wektor w = mnoz(pot(mfib(), poz, mod), wfib(), mod); REP(j, ilosc) { if (w.t[0] / (mod/10) == cyfra) { pom.push_back(poz + j * okres[i-1]); } w = mnoz(m, w, mod); } } potencjalni = pom; pom.clear(); } if (potencjalni.empty()) { puts("NIE"); } else { printf("%llu\n", potencjalni[0] + (unsigned long long)okres[n] * 2); } 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 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 | #include <cstdio> #include <cstring> #include <vector> using namespace std; #define REP(i,n) for(int i=0;i<(n);i++) #define FOR(a,b,c) for(int a=(b);a<=(c);a++) typedef long long ll; struct macierz{ macierz(ll a=0, ll b=0, ll c=0, ll d=0) { t[0][0] = a; t[0][1] = b; t[1][0] = c; t[1][1] = d; } ll t[2][2]; }; struct wektor{ wektor(ll a=0, ll b=0) { t[0] = a; t[1] = b; } ll t[2]; bool operator== (wektor const& a) { return a.t[0] == t[0] && a.t[1] == t[1]; } bool operator!= (wektor const& a) { return !(*this == a); } }; ll mnoz(ll a, ll b, ll mod) { ll res = 0; while (b) { if (b&1) res = res + a; if (res >= mod) res -= mod; a = a + a; if (a >= mod) a -= mod; b /= 2; } return res; } macierz zero() { return macierz(); } macierz jeden() { return macierz(1, 0, 0, 1); } macierz mnoz(macierz const& a, macierz const& b, ll mod) { macierz res = macierz(); REP(i,2) REP(j,2) REP(k,2) res.t[i][k] += mnoz(a.t[i][j], b.t[j][k], mod); REP(i,2) REP(j,2) res.t[i][j] %= mod; return res; } macierz pot(macierz a, ll b, ll mod) { macierz res = jeden(); while (b) { if (b&1) res = mnoz(res, a, mod); a = mnoz(a, a, mod); b /= 2; } return res; } wektor mnoz(macierz const& a, wektor const& b, ll mod) { wektor res = wektor(); REP(i,2) REP(j,2) res.t[i] += mnoz(a.t[i][j], b.t[j], mod); REP(i,2) res.t[i] %= mod; return res; } wektor wfib() { return wektor(0, 1); } macierz mfib() { return macierz(1, 1, 1, 0); } /*void wylicz() { wektor start = fib(); wektor fibw = start; ll mod = 1; ll okres = 1; FOR(i,1,18) { mod *= 10; macierz fibm = pot(fib(), okres, mod); int cnt = 1; fibw = mnoz(fibm, fibw, mod); while (fibw != start) { ++cnt; fibw = mnoz(fibm, fibw, mod); } okres *= cnt; printf("%lldLL,",okres); } }*/ ll okres[19] = {1,60LL,300LL,1500LL,15000LL,150000LL,1500000LL,15000000LL,150000000LL,1500000000LL,15000000000LL,150000000000LL,1500000000000LL,15000000000000LL,150000000000000LL,1500000000000000LL,15000000000000000LL,150000000000000000LL,1500000000000000000LL}; int main() { char cyf[100]; scanf("%s",cyf); int n = strlen(cyf); ll mod = 1; vector<ll> pom, potencjalni = {0}; FOR(i,1,n) { mod *= 10; int cyfra = cyf[n-i] - '0'; ll ilosc = okres[i] / okres[i-1]; macierz m = pot(mfib(), okres[i-1], mod); for (ll poz: potencjalni) { wektor w = mnoz(pot(mfib(), poz, mod), wfib(), mod); REP(j, ilosc) { if (w.t[0] / (mod/10) == cyfra) { pom.push_back(poz + j * okres[i-1]); } w = mnoz(m, w, mod); } } potencjalni = pom; pom.clear(); } if (potencjalni.empty()) { puts("NIE"); } else { printf("%llu\n", potencjalni[0] + (unsigned long long)okres[n] * 2); } return 0; } |