#include <algorithm> #include <cstdio> #include <cstring> #include <vector> typedef unsigned long long int BigInt; constexpr BigInt mod = 1000llu * 1000llu * 1000llu * 1000llu * 1000llu * 1000llu; // 10**18 BigInt SumModulo(BigInt a, BigInt b) { return (a + b) % mod; } BigInt MultiplicationModulo(BigInt a, BigInt b) { BigInt result = 0llu; while (a > 0) { if (a % 2 == 1) { result = SumModulo(result, b); } b = (b * 2) % mod; a /= 2; } return result; } constexpr BigInt Power(BigInt base, int exponent) { return exponent == 0 ? 1llu : base * Power(base, exponent - 1); } struct Matrix { BigInt a00_, a01_, a10_, a11_; Matrix(BigInt a00, BigInt a01, BigInt a10, BigInt a11) : a00_(a00), a01_(a01), a10_(a10), a11_(a11) {} Matrix(const Matrix& matrix) = default; Matrix(Matrix&& matrix) = default; Matrix& operator=(const Matrix& matrix) = default; Matrix operator * (const Matrix& matrix) const { return Matrix( SumModulo( MultiplicationModulo(a00_, matrix.a00_), MultiplicationModulo(a01_, matrix.a10_)), SumModulo( MultiplicationModulo(a00_, matrix.a01_), MultiplicationModulo(a01_, matrix.a11_)), SumModulo( MultiplicationModulo(a10_, matrix.a00_), MultiplicationModulo(a11_, matrix.a10_)), SumModulo( MultiplicationModulo(a10_, matrix.a01_), MultiplicationModulo(a11_, matrix.a11_))); } }; const int max_power = 105; std::vector<Matrix> all_powers; // On i-th position is Fib_matrix^(2^i). void PrepareAllPowers() { all_powers.emplace_back(0, 1, 1, 1); // Fib_matrix. for (int i = 1; i < max_power; i++) { all_powers.emplace_back(all_powers[i - 1] * all_powers[i - 1]); } } BigInt Fibonacci(BigInt f) { Matrix result(1, 0, 0, 1); int exponent = 0; while (f > 0) { if (f % 2 == 1) { result = result * all_powers[exponent]; } exponent++; f /= 2; } return result.a10_; } char number_as_string[18 + 5]; BigInt number; int n; constexpr int small = 3; constexpr BigInt small_limit = Power(10, small); constexpr BigInt small_cycle_length = small_limit * 15; BigInt limit = small_limit; BigInt fibonacci[small_cycle_length + 5]; void dfs(int depth, BigInt index, BigInt limit, BigInt cycle) { if (Fibonacci(index) % limit == number % limit) { if (depth >= n) { throw index; } const BigInt next_limit = limit * 10; const BigInt next_cycle = cycle * 10; for (int i = 0; i < 10; i++) { dfs(depth + 1, index += cycle, next_limit, next_cycle); } } } int main() { scanf("%s", number_as_string); n = strlen(number_as_string); sscanf(number_as_string, "%llu", &number); limit = std::min(limit, Power(10, n)); PrepareAllPowers(); fibonacci[0] = 0llu; fibonacci[1] = 1llu; try { for (int i = 0; i < small_cycle_length; i++) { if (i >= 2) { fibonacci[i] = SumModulo(fibonacci[i - 2], fibonacci[i - 1]); } if (fibonacci[i] % limit == number % limit) { dfs(small, i, limit, small_cycle_length); } } printf("NIE\n"); } catch (BigInt answer) { printf("1500000000000000000000000000000000000000%llu\n", answer); } 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 | #include <algorithm> #include <cstdio> #include <cstring> #include <vector> typedef unsigned long long int BigInt; constexpr BigInt mod = 1000llu * 1000llu * 1000llu * 1000llu * 1000llu * 1000llu; // 10**18 BigInt SumModulo(BigInt a, BigInt b) { return (a + b) % mod; } BigInt MultiplicationModulo(BigInt a, BigInt b) { BigInt result = 0llu; while (a > 0) { if (a % 2 == 1) { result = SumModulo(result, b); } b = (b * 2) % mod; a /= 2; } return result; } constexpr BigInt Power(BigInt base, int exponent) { return exponent == 0 ? 1llu : base * Power(base, exponent - 1); } struct Matrix { BigInt a00_, a01_, a10_, a11_; Matrix(BigInt a00, BigInt a01, BigInt a10, BigInt a11) : a00_(a00), a01_(a01), a10_(a10), a11_(a11) {} Matrix(const Matrix& matrix) = default; Matrix(Matrix&& matrix) = default; Matrix& operator=(const Matrix& matrix) = default; Matrix operator * (const Matrix& matrix) const { return Matrix( SumModulo( MultiplicationModulo(a00_, matrix.a00_), MultiplicationModulo(a01_, matrix.a10_)), SumModulo( MultiplicationModulo(a00_, matrix.a01_), MultiplicationModulo(a01_, matrix.a11_)), SumModulo( MultiplicationModulo(a10_, matrix.a00_), MultiplicationModulo(a11_, matrix.a10_)), SumModulo( MultiplicationModulo(a10_, matrix.a01_), MultiplicationModulo(a11_, matrix.a11_))); } }; const int max_power = 105; std::vector<Matrix> all_powers; // On i-th position is Fib_matrix^(2^i). void PrepareAllPowers() { all_powers.emplace_back(0, 1, 1, 1); // Fib_matrix. for (int i = 1; i < max_power; i++) { all_powers.emplace_back(all_powers[i - 1] * all_powers[i - 1]); } } BigInt Fibonacci(BigInt f) { Matrix result(1, 0, 0, 1); int exponent = 0; while (f > 0) { if (f % 2 == 1) { result = result * all_powers[exponent]; } exponent++; f /= 2; } return result.a10_; } char number_as_string[18 + 5]; BigInt number; int n; constexpr int small = 3; constexpr BigInt small_limit = Power(10, small); constexpr BigInt small_cycle_length = small_limit * 15; BigInt limit = small_limit; BigInt fibonacci[small_cycle_length + 5]; void dfs(int depth, BigInt index, BigInt limit, BigInt cycle) { if (Fibonacci(index) % limit == number % limit) { if (depth >= n) { throw index; } const BigInt next_limit = limit * 10; const BigInt next_cycle = cycle * 10; for (int i = 0; i < 10; i++) { dfs(depth + 1, index += cycle, next_limit, next_cycle); } } } int main() { scanf("%s", number_as_string); n = strlen(number_as_string); sscanf(number_as_string, "%llu", &number); limit = std::min(limit, Power(10, n)); PrepareAllPowers(); fibonacci[0] = 0llu; fibonacci[1] = 1llu; try { for (int i = 0; i < small_cycle_length; i++) { if (i >= 2) { fibonacci[i] = SumModulo(fibonacci[i - 2], fibonacci[i - 1]); } if (fibonacci[i] % limit == number % limit) { dfs(small, i, limit, small_cycle_length); } } printf("NIE\n"); } catch (BigInt answer) { printf("1500000000000000000000000000000000000000%llu\n", answer); } return 0; } |