#include <cstdio> #include <cstdlib> #include <queue> #include <algorithm> #include <cstring> #include <string> using namespace std; const long long max_mod = 1000000000000000000LL; // 10^18 const long long half_mod = 1000000000LL; // 10^9 struct fib { fib(long long p_f, long long p_prev) { f = p_f; prev = p_prev; } long long f, prev; }; struct results { results(fib p_f_k, int p_k, string p_extra_digs) : f_k(p_f_k) { k = p_k; extra_digs = p_extra_digs; } fib f_k; int k; string extra_digs; }; long long mul_mod(long long x, long long y) { long long x1 = x / half_mod; long long x2 = x % half_mod; long long y1 = y / half_mod; long long y2 = y % half_mod; return (((x1*y2 + x2*y1) % half_mod) * half_mod + x2*y2) % max_mod; } fib mul(fib f1, fib f2) { fib r(mul_mod(f1.f+f1.prev, f2.f) + mul_mod(f1.f, f2.prev), mul_mod(f1.f, f2.f) + mul_mod(f1.prev, f2.prev)); return r; } int main() { long long n; char s[20]; scanf("%s", s); int length = strlen(s); n = atoll(s); if (length == 1 && n == 0) { printf("0\n"); return 0; } long long f0 = 0, f1 = 1, f2; queue<results> q[2]; if (n % 10LL == 0) q[0].push(results(fib(0, 1), 0, string())); else if (n % 10LL == 1) q[0].push(results(fib(1, 0), 1, string())); for (int i = 2; i < 60; i++) { f2 = (f0 + f1); f0 = f1; f1 = f2; if (f1 % 10LL == n % 10LL) q[0].push(results(fib(f1, f0), i, string())); } long long mod = 100LL; fib step(f0 + f1, f1); // fib60 long long n10 = n / 10; int read_q = 0, write_q = 1; for (int i = 1; i < length; i++) { int steps = (mod <= 1000LL ? 5 : 10); int k_inc; if (mod == 100LL) k_inc = 6; else if (mod == 1000LL) k_inc = 3; else k_inc = 15; bool cut_digit = (mod != 10000LL); while (!q[read_q].empty()) { results r(q[read_q].front()); if (cut_digit) { r.extra_digs += ('0' + r.k % 10); r.k /= 10; } fib cand = r.f_k; if (cand.f % mod == n % mod) q[write_q].push(results(cand, r.k, r.extra_digs)); for (int i = 1; i < steps; i++) { cand = mul(cand, step); if (cand.f % mod == n % mod) q[write_q].push(results(cand, r.k + i*k_inc, r.extra_digs)); } q[read_q].pop(); } if (q[write_q].empty()) { printf("NIE\n"); return 0; } swap(read_q, write_q); mod *= 10LL; fib new_step = step; for (int i = 0; i < steps-1; i++) new_step = mul(new_step, step); step = new_step; n10 /= 10; } results final = q[read_q].front(); printf("%d", 60+final.k); for (int i = final.extra_digs.length()-1; i >= 0; i--) putchar(final.extra_digs[i]); putchar('\n'); //system("pause"); 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 | #include <cstdio> #include <cstdlib> #include <queue> #include <algorithm> #include <cstring> #include <string> using namespace std; const long long max_mod = 1000000000000000000LL; // 10^18 const long long half_mod = 1000000000LL; // 10^9 struct fib { fib(long long p_f, long long p_prev) { f = p_f; prev = p_prev; } long long f, prev; }; struct results { results(fib p_f_k, int p_k, string p_extra_digs) : f_k(p_f_k) { k = p_k; extra_digs = p_extra_digs; } fib f_k; int k; string extra_digs; }; long long mul_mod(long long x, long long y) { long long x1 = x / half_mod; long long x2 = x % half_mod; long long y1 = y / half_mod; long long y2 = y % half_mod; return (((x1*y2 + x2*y1) % half_mod) * half_mod + x2*y2) % max_mod; } fib mul(fib f1, fib f2) { fib r(mul_mod(f1.f+f1.prev, f2.f) + mul_mod(f1.f, f2.prev), mul_mod(f1.f, f2.f) + mul_mod(f1.prev, f2.prev)); return r; } int main() { long long n; char s[20]; scanf("%s", s); int length = strlen(s); n = atoll(s); if (length == 1 && n == 0) { printf("0\n"); return 0; } long long f0 = 0, f1 = 1, f2; queue<results> q[2]; if (n % 10LL == 0) q[0].push(results(fib(0, 1), 0, string())); else if (n % 10LL == 1) q[0].push(results(fib(1, 0), 1, string())); for (int i = 2; i < 60; i++) { f2 = (f0 + f1); f0 = f1; f1 = f2; if (f1 % 10LL == n % 10LL) q[0].push(results(fib(f1, f0), i, string())); } long long mod = 100LL; fib step(f0 + f1, f1); // fib60 long long n10 = n / 10; int read_q = 0, write_q = 1; for (int i = 1; i < length; i++) { int steps = (mod <= 1000LL ? 5 : 10); int k_inc; if (mod == 100LL) k_inc = 6; else if (mod == 1000LL) k_inc = 3; else k_inc = 15; bool cut_digit = (mod != 10000LL); while (!q[read_q].empty()) { results r(q[read_q].front()); if (cut_digit) { r.extra_digs += ('0' + r.k % 10); r.k /= 10; } fib cand = r.f_k; if (cand.f % mod == n % mod) q[write_q].push(results(cand, r.k, r.extra_digs)); for (int i = 1; i < steps; i++) { cand = mul(cand, step); if (cand.f % mod == n % mod) q[write_q].push(results(cand, r.k + i*k_inc, r.extra_digs)); } q[read_q].pop(); } if (q[write_q].empty()) { printf("NIE\n"); return 0; } swap(read_q, write_q); mod *= 10LL; fib new_step = step; for (int i = 0; i < steps-1; i++) new_step = mul(new_step, step); step = new_step; n10 /= 10; } results final = q[read_q].front(); printf("%d", 60+final.k); for (int i = final.extra_digs.length()-1; i >= 0; i--) putchar(final.extra_digs[i]); putchar('\n'); //system("pause"); return 0; } |