//Pawel Kura #ifdef DEBUG const bool deb = true; #else const bool deb = false; #endif #include <cstdio> #include <cassert> #include <vector> #include <algorithm> #include <cstring> using namespace std; typedef long long LL; LL fib[400]; LL T[20]; LL pot[20]; char s[30]; int a[30]; int n; inline LL mul(LL a, LL b) { LL A = a / pot[9]; LL B = a % pot[9]; LL C = b / pot[9]; LL D = b % pot[9]; return (pot[9] * ( ((A*D) % pot[9]) + ((B*C) % pot[9])) + B * D) % pot[18]; } inline int digit(LL x, int k) { if (deb) assert(k <= 18); return (x / pot[k]) % 10; } LL fm[2][2] = { {0, 1}, {1, 1} }; LL res[2][2]; LL tmp[2][2]; void mulmat(LL a[2][2], LL b[2][2]) { tmp[0][0] = tmp[0][1] = tmp[1][0] = tmp[1][1] = 0; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) tmp[i][j] = (tmp[i][j] + mul(a[i][k], b[k][j])) % pot[18]; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) a[i][j] = tmp[i][j]; } LL F(LL x) { res[0][0] = res[1][1] = 1; res[0][1] = res[1][0] = 0; for (int i = 61; i >= 0; i--) { mulmat(res, res); if (x & (1LL<<i)) { mulmat(res, fm); } } return res[1][0]; } void rozwal() { scanf("%s", s); n = strlen(s); for (int i = n-1; i >= 0; i--) a[n - i - 1] = s[i] - '0'; vector<pair<LL, LL>> cands[30]; //cands.insert({0, 0}); cands[0].push_back({0, 0}); for (int i = 1; i <= n; i++) { for (auto p: cands[i - 1]) { if (digit(p.second, i - 1) == a[i-1]) cands[i].push_back(p); for (int d = 1; d < T[i]/T[i-1]; d++) { LL ind = p.first + d * T[i-1]; LL f = F(ind); if (digit(f, i - 1) == a[i-1]) cands[i].push_back({ind, f}); } } sort(begin(cands[i]), end(cands[i])); cands[i].resize(unique(begin(cands[i]), end(cands[i])) - begin(cands[i])); } if (cands[n].size() == 0) puts("NIE"); else { LL ind = cands[n][0].first; LL fib = cands[n][0].second; LL ind2 = ind + T[18]; if (deb) { LL fib2 = F(ind2); assert(fib2 == fib); fprintf(stderr, "q = %s\n", s); fprintf(stderr, "fib(%lld) = %lld\n", ind, fib); fprintf(stderr, "fib(%lld) = %lld\n", ind2, fib2); } printf("%lld\n", ind2); } } int main() { T[0] = 1; T[1] = 60; T[2] = 300; T[3] = 1500; for (int i = 4; i <= 18; i++) T[i] = T[i-1] * 10; pot[0] = 1; for (int i = 1; i <= 18; i++) pot[i] = 10 * pot[i-1]; int tests; if (!deb) tests = 1; else tests = 36; while (tests--) rozwal(); 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 | //Pawel Kura #ifdef DEBUG const bool deb = true; #else const bool deb = false; #endif #include <cstdio> #include <cassert> #include <vector> #include <algorithm> #include <cstring> using namespace std; typedef long long LL; LL fib[400]; LL T[20]; LL pot[20]; char s[30]; int a[30]; int n; inline LL mul(LL a, LL b) { LL A = a / pot[9]; LL B = a % pot[9]; LL C = b / pot[9]; LL D = b % pot[9]; return (pot[9] * ( ((A*D) % pot[9]) + ((B*C) % pot[9])) + B * D) % pot[18]; } inline int digit(LL x, int k) { if (deb) assert(k <= 18); return (x / pot[k]) % 10; } LL fm[2][2] = { {0, 1}, {1, 1} }; LL res[2][2]; LL tmp[2][2]; void mulmat(LL a[2][2], LL b[2][2]) { tmp[0][0] = tmp[0][1] = tmp[1][0] = tmp[1][1] = 0; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) tmp[i][j] = (tmp[i][j] + mul(a[i][k], b[k][j])) % pot[18]; for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) a[i][j] = tmp[i][j]; } LL F(LL x) { res[0][0] = res[1][1] = 1; res[0][1] = res[1][0] = 0; for (int i = 61; i >= 0; i--) { mulmat(res, res); if (x & (1LL<<i)) { mulmat(res, fm); } } return res[1][0]; } void rozwal() { scanf("%s", s); n = strlen(s); for (int i = n-1; i >= 0; i--) a[n - i - 1] = s[i] - '0'; vector<pair<LL, LL>> cands[30]; //cands.insert({0, 0}); cands[0].push_back({0, 0}); for (int i = 1; i <= n; i++) { for (auto p: cands[i - 1]) { if (digit(p.second, i - 1) == a[i-1]) cands[i].push_back(p); for (int d = 1; d < T[i]/T[i-1]; d++) { LL ind = p.first + d * T[i-1]; LL f = F(ind); if (digit(f, i - 1) == a[i-1]) cands[i].push_back({ind, f}); } } sort(begin(cands[i]), end(cands[i])); cands[i].resize(unique(begin(cands[i]), end(cands[i])) - begin(cands[i])); } if (cands[n].size() == 0) puts("NIE"); else { LL ind = cands[n][0].first; LL fib = cands[n][0].second; LL ind2 = ind + T[18]; if (deb) { LL fib2 = F(ind2); assert(fib2 == fib); fprintf(stderr, "q = %s\n", s); fprintf(stderr, "fib(%lld) = %lld\n", ind, fib); fprintf(stderr, "fib(%lld) = %lld\n", ind2, fib2); } printf("%lld\n", ind2); } } int main() { T[0] = 1; T[1] = 60; T[2] = 300; T[3] = 1500; for (int i = 4; i <= 18; i++) T[i] = T[i-1] * 10; pot[0] = 1; for (int i = 1; i <= 18; i++) pot[i] = 10 * pot[i-1]; int tests; if (!deb) tests = 1; else tests = 36; while (tests--) rozwal(); return 0; } |