#include <iostream> #include <array> constexpr uint64_t mynum[21] = { 1ULL, 60ULL, 300ULL, 1500ULL, 15000ULL, 150000ULL, 1500000ULL, 15000000ULL, 150000000ULL, 1500000000ULL, 15000000000ULL, 150000000000ULL, 1500000000000ULL, 15000000000000ULL, 150000000000000ULL, 1500000000000000ULL, 15000000000000000ULL, 150000000000000000ULL, 1500000000000000000ULL, 15000000000000000000ULL }; uint64_t szukana = 0, m = 1; class matrix { public: std::array<uint64_t, 4> v; matrix operator*(const matrix& x) const { return {(v[0] * x.v[0] + v[1] * x.v[2])%m, (v[0] * x.v[1] + v[1] * x.v[3])%m, (v[2] * x.v[0] + v[3]* x.v[2])%m, (v[2] * x.v[1] + v[3] * x.v[3])%m}; } }; matrix square(const matrix& x) { return x*x; } matrix fast_pow(matrix x, uint64_t n) { if(n==0) { return {1, 0, 0, 1}; } if(n%2 == 1) { return x * square(fast_pow(x, n/2)); } return square(fast_pow(x, n/2)); } uint64_t fib(uint64_t i) { return fast_pow({1, 1, 1, 0}, i).v[1]; } uint64_t find(uint64_t i = 120, uint64_t temp_mod = 10, unsigned depth = 0) { //std::cerr << i << ": " << fib(i) << "~" <<szukana << '\n'; if(fib(i) == szukana) return i; const uint64_t to_add = mynum[depth]; for(unsigned t = 0; t < 150; ++t) { if(fib(i)%temp_mod == szukana%temp_mod) { const uint64_t answer = find(i, temp_mod * 10, depth + 1); if(answer != 0) { return answer; } } i += to_add; } return 0; } int main() { std::string szukany; std::cin >> szukany; for(size_t i = 0; i < szukany.size(); ++i) { szukana += m * (szukany[szukany.size() - (1+i)]-'0'); m *= 10; } const uint64_t answer = find(); if(answer == 0) { std::cout << "NIE\n"; return 0; } std::cout << answer << '\n'; }
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 | #include <iostream> #include <array> constexpr uint64_t mynum[21] = { 1ULL, 60ULL, 300ULL, 1500ULL, 15000ULL, 150000ULL, 1500000ULL, 15000000ULL, 150000000ULL, 1500000000ULL, 15000000000ULL, 150000000000ULL, 1500000000000ULL, 15000000000000ULL, 150000000000000ULL, 1500000000000000ULL, 15000000000000000ULL, 150000000000000000ULL, 1500000000000000000ULL, 15000000000000000000ULL }; uint64_t szukana = 0, m = 1; class matrix { public: std::array<uint64_t, 4> v; matrix operator*(const matrix& x) const { return {(v[0] * x.v[0] + v[1] * x.v[2])%m, (v[0] * x.v[1] + v[1] * x.v[3])%m, (v[2] * x.v[0] + v[3]* x.v[2])%m, (v[2] * x.v[1] + v[3] * x.v[3])%m}; } }; matrix square(const matrix& x) { return x*x; } matrix fast_pow(matrix x, uint64_t n) { if(n==0) { return {1, 0, 0, 1}; } if(n%2 == 1) { return x * square(fast_pow(x, n/2)); } return square(fast_pow(x, n/2)); } uint64_t fib(uint64_t i) { return fast_pow({1, 1, 1, 0}, i).v[1]; } uint64_t find(uint64_t i = 120, uint64_t temp_mod = 10, unsigned depth = 0) { //std::cerr << i << ": " << fib(i) << "~" <<szukana << '\n'; if(fib(i) == szukana) return i; const uint64_t to_add = mynum[depth]; for(unsigned t = 0; t < 150; ++t) { if(fib(i)%temp_mod == szukana%temp_mod) { const uint64_t answer = find(i, temp_mod * 10, depth + 1); if(answer != 0) { return answer; } } i += to_add; } return 0; } int main() { std::string szukany; std::cin >> szukany; for(size_t i = 0; i < szukany.size(); ++i) { szukana += m * (szukany[szukany.size() - (1+i)]-'0'); m *= 10; } const uint64_t answer = find(); if(answer == 0) { std::cout << "NIE\n"; return 0; } std::cout << answer << '\n'; } |