#ifndef DEBUG_MODE #define NDEBUG #endif #include <vector> #include <string> #include <iostream> #include <algorithm> #include <cstdio> using namespace std; typedef unsigned long long ull; ull mul(ull a, ull b, ull mod) { ull result; if(b == 0) return 0LL; result = mul(a, b >> 1, mod); result = (result + result) % mod; if(b & 1) result = (result + a) % mod; return result; } void mul(ull f[2][2], ull m[2][2], ull mod) { ull x = (mul(f[0][0], m[0][0], mod) + mul(f[0][1], m[1][0], mod)) % mod; ull y = (mul(f[0][0], m[0][1], mod) + mul(f[0][1], m[1][1], mod)) % mod; ull z = (mul(f[1][0], m[0][0], mod) + mul(f[1][1], m[1][0], mod)) % mod; ull w = (mul(f[1][0], m[0][1], mod) + mul(f[1][1], m[1][1], mod)) % mod; f[0][0] = x; f[0][1] = y; f[1][0] = z; f[1][1] = w; } void power(ull f[2][2], ull n, ull mod) { if(n == 0 || n == 1) return; ull m[2][2] = {{1, 1}, {1, 0}}; power(f, n / 2, mod); mul(f, f, mod); if(n % 2 != 0) mul(f, m, mod); } // Even better: http://codeforces.com/blog/entry/14516 ull fib(ull n, ull mod) { ull f[2][2] = {{1, 1}, {1, 0}}; if(n == 0) return 0; power(f, n - 1, mod); return f[0][0]; } typedef vector<pair<ull, ull>> FibPairs; ull modCycle(ull mod) { return mod == 10 ? 60 : mod == 100 ? 300 : mod + mod / 2; } FibPairs computeAll(ull mod, ull value) { ull a = 0, b = 1; ull max_count = modCycle(mod); ull val_mod = value % mod; FibPairs out; if(val_mod == 0) out.push_back(make_pair(0ll, 0ll)); if(val_mod == 1) out.push_back(make_pair(1ll, 1ll)); for(int k = 0; k < max_count; k++) { ull next = (a + b) % mod; a = b; b = next; if(next == val_mod) out.push_back(make_pair(k + 2, next)); } return out; } int main() { string svalue; cin >> svalue; if(svalue.empty()) return false; ull target_mod = 1, value; for(int n = 0; n < (int)svalue.size(); n++) target_mod *= 10; sscanf(svalue.c_str(), "%llu", &value); ull mod = 10; FibPairs vals = computeAll(mod, value); #ifdef DEBUG_MODE printf("Value: %llu mod: %llu\n", value, target_mod); #endif while(mod < target_mod) { #ifdef DEBUG_MODE printf("Step: %lld -> %lld\n", mod, mod * 10); #endif FibPairs new_vals; ull next_mod = mod * 10; ull cur_cycle = modCycle(mod), next_cycle = modCycle(next_mod); ull steps = next_cycle / cur_cycle; ull val_mod = value % next_mod; for(int n = 0; n < (int)vals.size(); n++) { #ifdef DEBUG_MODE printf("%lld: %lld\n", vals[n].first, vals[n].second); #endif ull k = vals[n].first; for(ull i = 0; i < steps; i++) { ull k = vals[n].first + cur_cycle * i; ull f = fib(k, next_mod); if(f == val_mod) { new_vals.push_back(make_pair(k, f)); } } } #ifdef DEBUG_MODE printf("\n"); #endif vals.swap(new_vals); mod = next_mod; } if(vals.empty()) cout << "NIE" << endl; else { std::sort(vals.begin(), vals.end()); cout << vals.front().first << 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 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 | #ifndef DEBUG_MODE #define NDEBUG #endif #include <vector> #include <string> #include <iostream> #include <algorithm> #include <cstdio> using namespace std; typedef unsigned long long ull; ull mul(ull a, ull b, ull mod) { ull result; if(b == 0) return 0LL; result = mul(a, b >> 1, mod); result = (result + result) % mod; if(b & 1) result = (result + a) % mod; return result; } void mul(ull f[2][2], ull m[2][2], ull mod) { ull x = (mul(f[0][0], m[0][0], mod) + mul(f[0][1], m[1][0], mod)) % mod; ull y = (mul(f[0][0], m[0][1], mod) + mul(f[0][1], m[1][1], mod)) % mod; ull z = (mul(f[1][0], m[0][0], mod) + mul(f[1][1], m[1][0], mod)) % mod; ull w = (mul(f[1][0], m[0][1], mod) + mul(f[1][1], m[1][1], mod)) % mod; f[0][0] = x; f[0][1] = y; f[1][0] = z; f[1][1] = w; } void power(ull f[2][2], ull n, ull mod) { if(n == 0 || n == 1) return; ull m[2][2] = {{1, 1}, {1, 0}}; power(f, n / 2, mod); mul(f, f, mod); if(n % 2 != 0) mul(f, m, mod); } // Even better: http://codeforces.com/blog/entry/14516 ull fib(ull n, ull mod) { ull f[2][2] = {{1, 1}, {1, 0}}; if(n == 0) return 0; power(f, n - 1, mod); return f[0][0]; } typedef vector<pair<ull, ull>> FibPairs; ull modCycle(ull mod) { return mod == 10 ? 60 : mod == 100 ? 300 : mod + mod / 2; } FibPairs computeAll(ull mod, ull value) { ull a = 0, b = 1; ull max_count = modCycle(mod); ull val_mod = value % mod; FibPairs out; if(val_mod == 0) out.push_back(make_pair(0ll, 0ll)); if(val_mod == 1) out.push_back(make_pair(1ll, 1ll)); for(int k = 0; k < max_count; k++) { ull next = (a + b) % mod; a = b; b = next; if(next == val_mod) out.push_back(make_pair(k + 2, next)); } return out; } int main() { string svalue; cin >> svalue; if(svalue.empty()) return false; ull target_mod = 1, value; for(int n = 0; n < (int)svalue.size(); n++) target_mod *= 10; sscanf(svalue.c_str(), "%llu", &value); ull mod = 10; FibPairs vals = computeAll(mod, value); #ifdef DEBUG_MODE printf("Value: %llu mod: %llu\n", value, target_mod); #endif while(mod < target_mod) { #ifdef DEBUG_MODE printf("Step: %lld -> %lld\n", mod, mod * 10); #endif FibPairs new_vals; ull next_mod = mod * 10; ull cur_cycle = modCycle(mod), next_cycle = modCycle(next_mod); ull steps = next_cycle / cur_cycle; ull val_mod = value % next_mod; for(int n = 0; n < (int)vals.size(); n++) { #ifdef DEBUG_MODE printf("%lld: %lld\n", vals[n].first, vals[n].second); #endif ull k = vals[n].first; for(ull i = 0; i < steps; i++) { ull k = vals[n].first + cur_cycle * i; ull f = fib(k, next_mod); if(f == val_mod) { new_vals.push_back(make_pair(k, f)); } } } #ifdef DEBUG_MODE printf("\n"); #endif vals.swap(new_vals); mod = next_mod; } if(vals.empty()) cout << "NIE" << endl; else { std::sort(vals.begin(), vals.end()); cout << vals.front().first << endl; } return 0; } |