#include <iostream> #include <vector> using namespace std; struct DuzaLiczba { long long l[2]; const static long long mod = 1000000000; DuzaLiczba(): DuzaLiczba(0) {} DuzaLiczba(long long liczba) { l[0] = liczba / mod; l[1] = liczba % mod; } DuzaLiczba operator*(const DuzaLiczba& l2) const { DuzaLiczba d = 0; d.l[0] = l[0] * l2.l[1] + l[1] * l2.l[0]; d.l[1] = l[1] * l2.l[1]; d.l[0] = (d.l[0] + d.l[1] / mod) % mod; d.l[1] = d.l[1] % mod; return d; } DuzaLiczba operator+(const DuzaLiczba& l2) const { DuzaLiczba d = 0; d.l[0] = l[0] + l2.l[0]; d.l[1] = l[1] + l2.l[1]; d.l[0] = (d.l[0] + d.l[1] / mod) % mod; d.l[1] = d.l[1] % mod; return d; } long long operator%(long long l2) const { return (l[0] * mod + l[1]) % l2; } friend ostream& operator<<(ostream& os, const DuzaLiczba& l) { return os << l.l[0] * l.mod + l.l[1]; } }; struct S { DuzaLiczba t[2][2]; S(): S(1, 0, 0, 1) {} S(long long a, long long b, long long c, long long d) :t({{a,b},{c,d}}) { } S operator*(const S& s2) { S s; s.t[0][0] = t[0][0] * s2.t[0][0] + t[0][1] * s2.t[1][0]; s.t[0][1] = t[0][0] * s2.t[0][1] + t[0][1] * s2.t[1][1]; s.t[1][0] = t[1][0] * s2.t[0][0] + t[1][1] * s2.t[1][0]; s.t[1][1] = t[1][0] * s2.t[0][1] + t[1][1] * s2.t[1][1]; return s; } }; S pot[100]; long long k[20]; S tab[20]; vector <pair <long long, S> > v[20]; int main() { pot[1] = {1, 1, 1, 0}; for(int i = 2; i <= 60; i ++) { pot[i] = pot[i - 1] * pot[i - 1]; } k[0] = 1; k[1] = 60; k[2] = 300; k[3] = 1500; for(int i = 4; i <= 18; i ++) { k[i] = k[i - 1] * 10; } for(int i = 0; i <= 18; i ++) { long long m = k[i]; int x = 1; tab[i] = pot[0]; while(m) { if(m % 2) { tab[i] = tab[i] * pot[x]; } x ++; m /= 2; } } string s; cin >> s; long long mod = 1; long long c = 0; v[0].emplace_back(0, pot[0]); for(int i = 0; i < s.size(); i ++) { c += (s[s.size() - i - 1] - '0') * mod; mod *= 10; for(int j = 0; j < v[i].size(); j ++) { S t = v[i][j].second; for(long long nr = v[i][j].first; nr < k[i + 1]; nr += k[i]) { if(t.t[0][1] % mod == c) { v[i + 1].emplace_back(nr, t); } t = t * tab[i]; } } } if(v[s.size()].size()) { cout << v[s.size()][0].first + k[s.size()] << endl; } else { cout << "NIE" << endl; } 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 | #include <iostream> #include <vector> using namespace std; struct DuzaLiczba { long long l[2]; const static long long mod = 1000000000; DuzaLiczba(): DuzaLiczba(0) {} DuzaLiczba(long long liczba) { l[0] = liczba / mod; l[1] = liczba % mod; } DuzaLiczba operator*(const DuzaLiczba& l2) const { DuzaLiczba d = 0; d.l[0] = l[0] * l2.l[1] + l[1] * l2.l[0]; d.l[1] = l[1] * l2.l[1]; d.l[0] = (d.l[0] + d.l[1] / mod) % mod; d.l[1] = d.l[1] % mod; return d; } DuzaLiczba operator+(const DuzaLiczba& l2) const { DuzaLiczba d = 0; d.l[0] = l[0] + l2.l[0]; d.l[1] = l[1] + l2.l[1]; d.l[0] = (d.l[0] + d.l[1] / mod) % mod; d.l[1] = d.l[1] % mod; return d; } long long operator%(long long l2) const { return (l[0] * mod + l[1]) % l2; } friend ostream& operator<<(ostream& os, const DuzaLiczba& l) { return os << l.l[0] * l.mod + l.l[1]; } }; struct S { DuzaLiczba t[2][2]; S(): S(1, 0, 0, 1) {} S(long long a, long long b, long long c, long long d) :t({{a,b},{c,d}}) { } S operator*(const S& s2) { S s; s.t[0][0] = t[0][0] * s2.t[0][0] + t[0][1] * s2.t[1][0]; s.t[0][1] = t[0][0] * s2.t[0][1] + t[0][1] * s2.t[1][1]; s.t[1][0] = t[1][0] * s2.t[0][0] + t[1][1] * s2.t[1][0]; s.t[1][1] = t[1][0] * s2.t[0][1] + t[1][1] * s2.t[1][1]; return s; } }; S pot[100]; long long k[20]; S tab[20]; vector <pair <long long, S> > v[20]; int main() { pot[1] = {1, 1, 1, 0}; for(int i = 2; i <= 60; i ++) { pot[i] = pot[i - 1] * pot[i - 1]; } k[0] = 1; k[1] = 60; k[2] = 300; k[3] = 1500; for(int i = 4; i <= 18; i ++) { k[i] = k[i - 1] * 10; } for(int i = 0; i <= 18; i ++) { long long m = k[i]; int x = 1; tab[i] = pot[0]; while(m) { if(m % 2) { tab[i] = tab[i] * pot[x]; } x ++; m /= 2; } } string s; cin >> s; long long mod = 1; long long c = 0; v[0].emplace_back(0, pot[0]); for(int i = 0; i < s.size(); i ++) { c += (s[s.size() - i - 1] - '0') * mod; mod *= 10; for(int j = 0; j < v[i].size(); j ++) { S t = v[i][j].second; for(long long nr = v[i][j].first; nr < k[i + 1]; nr += k[i]) { if(t.t[0][1] % mod == c) { v[i + 1].emplace_back(nr, t); } t = t * tab[i]; } } } if(v[s.size()].size()) { cout << v[s.size()][0].first + k[s.size()] << endl; } else { cout << "NIE" << endl; } return 0; } |