#include <cstdio> #include <cstdlib> #include <string> #include <vector> using namespace std; typedef long long i64; typedef unsigned long long u64; template<typename T> inline T pow2(int e) { return T(1) << e; } struct M22 { M22(i64 a11, i64 a12, i64 a21, i64 a22) : a11_(a11), a12_(a12), a21_(a21), a22_(a22) {} i64 a11_, a12_, a21_, a22_; }; u64 mltp64(u64 x, u64 y, u64 m) { if (x == 0 || y == 0) return 0; int t[18]; int k = 0; while (x != 0) { t[k++] = x%10; x /= 10; } u64 r = 0; for (int i=k-1; i>=0; --i) { r = (r*10) % m; r = (r + y*t[i]) % m; } return r; } M22 multiply(const M22& x, const M22& y, i64 m) { return M22((mltp64(x.a11_,y.a11_,m) + mltp64(x.a12_,y.a21_,m)) % m, (mltp64(x.a11_,y.a12_,m) + mltp64(x.a12_,y.a22_,m)) % m, (mltp64(x.a21_,y.a11_,m) + mltp64(x.a22_,y.a21_,m)) % m, (mltp64(x.a21_,y.a12_,m) + mltp64(x.a22_,y.a22_,m)) % m); } M22 pow(const M22& x, u64 e, i64 m) { M22 y(1,0,0,1); if (e == 0) return y; for (int i=63-__builtin_clzll(e); i>=0; --i) { y = multiply(y,y,m); if (e & pow2<u64>(i)) y = multiply(y,x,m); } return y; } i64 fib(i64 n, i64 m) { return pow(M22(0,1,1,1), n, m).a12_; } i64 solve(i64 r, int n) { i64 p10 = 1000; if (n == 1) p10 = 10; else if (n == 2) p10 = 100; i64 p15 = 1500; i64 r10 = r%p10; vector<i64> qs; for (i64 i=0; i<p15; ++i) if (fib(i, p10) == r10) qs.push_back(i); for (int i=4; i<=n; ++i) { p10 *= 10; r10 = r%p10; vector<i64> nqs; for (i64 q : qs) for (int j=0; j<10; ++j) if (fib(p15*j+q, p10) == r10) nqs.push_back(p15*j+q); p15 *= 10; qs = move(nqs); } if (qs.empty()) return -1; return qs[0] + 1500000000000000000ll; } int main() { char tmp[20]; scanf("%s", tmp); string s(tmp); i64 q = solve(atoll(s.c_str()), (int)s.size()); if (q == -1) printf("NIE\n"); else printf("%lld\n", q); }
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 | #include <cstdio> #include <cstdlib> #include <string> #include <vector> using namespace std; typedef long long i64; typedef unsigned long long u64; template<typename T> inline T pow2(int e) { return T(1) << e; } struct M22 { M22(i64 a11, i64 a12, i64 a21, i64 a22) : a11_(a11), a12_(a12), a21_(a21), a22_(a22) {} i64 a11_, a12_, a21_, a22_; }; u64 mltp64(u64 x, u64 y, u64 m) { if (x == 0 || y == 0) return 0; int t[18]; int k = 0; while (x != 0) { t[k++] = x%10; x /= 10; } u64 r = 0; for (int i=k-1; i>=0; --i) { r = (r*10) % m; r = (r + y*t[i]) % m; } return r; } M22 multiply(const M22& x, const M22& y, i64 m) { return M22((mltp64(x.a11_,y.a11_,m) + mltp64(x.a12_,y.a21_,m)) % m, (mltp64(x.a11_,y.a12_,m) + mltp64(x.a12_,y.a22_,m)) % m, (mltp64(x.a21_,y.a11_,m) + mltp64(x.a22_,y.a21_,m)) % m, (mltp64(x.a21_,y.a12_,m) + mltp64(x.a22_,y.a22_,m)) % m); } M22 pow(const M22& x, u64 e, i64 m) { M22 y(1,0,0,1); if (e == 0) return y; for (int i=63-__builtin_clzll(e); i>=0; --i) { y = multiply(y,y,m); if (e & pow2<u64>(i)) y = multiply(y,x,m); } return y; } i64 fib(i64 n, i64 m) { return pow(M22(0,1,1,1), n, m).a12_; } i64 solve(i64 r, int n) { i64 p10 = 1000; if (n == 1) p10 = 10; else if (n == 2) p10 = 100; i64 p15 = 1500; i64 r10 = r%p10; vector<i64> qs; for (i64 i=0; i<p15; ++i) if (fib(i, p10) == r10) qs.push_back(i); for (int i=4; i<=n; ++i) { p10 *= 10; r10 = r%p10; vector<i64> nqs; for (i64 q : qs) for (int j=0; j<10; ++j) if (fib(p15*j+q, p10) == r10) nqs.push_back(p15*j+q); p15 *= 10; qs = move(nqs); } if (qs.empty()) return -1; return qs[0] + 1500000000000000000ll; } int main() { char tmp[20]; scanf("%s", tmp); string s(tmp); i64 q = solve(atoll(s.c_str()), (int)s.size()); if (q == -1) printf("NIE\n"); else printf("%lld\n", q); } |