#include <iostream> #include <string> #include <cctype> #include <vector> #include <string.h> #define SIZE_OF_ARRAY(x) (sizeof(x) / sizeof(*(x))) #ifndef _MSC_VER #define __int64 long long #endif typedef unsigned int uint; typedef unsigned __int64 uint64; static char put_uint64_buffer[20] = "..................."; static char find_buffer[20] = "..................."; uint find_idx; bool find_uint64(uint64 value, bool fill_dot, bool fill_0) { int i; if (value == 0) { put_uint64_buffer[i = (SIZE_OF_ARRAY(put_uint64_buffer) - 1)] = '0'; } else { for (i = SIZE_OF_ARRAY(put_uint64_buffer); fill_0 ? (i > 14) : (value != 0); value /= 10) { put_uint64_buffer[--i] = '0' + (value % 10); } } if (fill_dot) { i = 0; } if (memcmp(find_buffer + find_idx, put_uint64_buffer + i + find_idx, SIZE_OF_ARRAY(put_uint64_buffer) - i - find_idx) == 0) { return true; } return false; } uint64 fib_mod = 1000000000000000000; uint fib_fill_idx = 85; void find_fib(uint max_k) { uint64 f[2] = { 0, 1 }; uint idx = 1; uint k = 2; while (k < max_k) { idx = 1 - idx; // put_uint64(fib.size(), false, false); std::cout.put(' '); if (find_uint64(f[idx] = (f[0] + f[1]) % fib_mod, true, k > fib_fill_idx)) { std::cout << k << '\n'; return; } ++k; } std::cout << "NIE\n"; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); while (isspace(std::cin.get())); std::cin.unget(); char tmp[32]; std::cin.getline(tmp, 32); uint n = std::cin.gcount(); find_idx = SIZE_OF_ARRAY(find_buffer) - n + 1; for (uint i = 0; i < n; ++i) { find_buffer[SIZE_OF_ARRAY(find_buffer) - n + 1 + i] = tmp[i]; } find_fib(2000000); 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 | #include <iostream> #include <string> #include <cctype> #include <vector> #include <string.h> #define SIZE_OF_ARRAY(x) (sizeof(x) / sizeof(*(x))) #ifndef _MSC_VER #define __int64 long long #endif typedef unsigned int uint; typedef unsigned __int64 uint64; static char put_uint64_buffer[20] = "..................."; static char find_buffer[20] = "..................."; uint find_idx; bool find_uint64(uint64 value, bool fill_dot, bool fill_0) { int i; if (value == 0) { put_uint64_buffer[i = (SIZE_OF_ARRAY(put_uint64_buffer) - 1)] = '0'; } else { for (i = SIZE_OF_ARRAY(put_uint64_buffer); fill_0 ? (i > 14) : (value != 0); value /= 10) { put_uint64_buffer[--i] = '0' + (value % 10); } } if (fill_dot) { i = 0; } if (memcmp(find_buffer + find_idx, put_uint64_buffer + i + find_idx, SIZE_OF_ARRAY(put_uint64_buffer) - i - find_idx) == 0) { return true; } return false; } uint64 fib_mod = 1000000000000000000; uint fib_fill_idx = 85; void find_fib(uint max_k) { uint64 f[2] = { 0, 1 }; uint idx = 1; uint k = 2; while (k < max_k) { idx = 1 - idx; // put_uint64(fib.size(), false, false); std::cout.put(' '); if (find_uint64(f[idx] = (f[0] + f[1]) % fib_mod, true, k > fib_fill_idx)) { std::cout << k << '\n'; return; } ++k; } std::cout << "NIE\n"; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); while (isspace(std::cin.get())); std::cin.unget(); char tmp[32]; std::cin.getline(tmp, 32); uint n = std::cin.gcount(); find_idx = SIZE_OF_ARRAY(find_buffer) - n + 1; for (uint i = 0; i < n; ++i) { find_buffer[SIZE_OF_ARRAY(find_buffer) - n + 1 + i] = tmp[i]; } find_fib(2000000); return 0; } |