#include <cstdio> #include <cstdlib> #include <cstring> using namespace std; const int kMaxLength = 18; const long long kPisano = 1500LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL; long long Add(long long a, long long b, long long m) { return (a + b) % m; } // http://stackoverflow.com/questions/12168348/ways-to-do-modulo-multiplication-with-primitive-types long long mulmod(long long a, long long b, long long m) { long long res = 0; while (a != 0) { if (a & 1) res = (res + b) % m; a >>= 1; b = (b << 1) % m; } return res; } class Transformation { public: Transformation() : a00_(0), a01_(1), a10_(1), a11_(1) {} long long a00() const { return a00_; } long long a01() const { return a01_; } long long a10() const { return a10_; } long long a11() const { return a11_; } static Transformation Multiply(const Transformation& a, const Transformation& b, const long long modulus) { return Transformation( Add(mulmod(a.a00(), b.a00(), modulus), mulmod(a.a01(), b.a10(), modulus), modulus), Add(mulmod(a.a00(), b.a01(), modulus), mulmod(a.a01(), b.a11(), modulus), modulus), Add(mulmod(a.a10(), b.a00(), modulus), mulmod(a.a11(), b.a10(), modulus), modulus), Add(mulmod(a.a10(), b.a01(), modulus), mulmod(a.a11(), b.a11(), modulus), modulus)); } Transformation Power(const long long exponent, const long long modulus) const { if (exponent == 0) return Transformation(1, 0, 0, 1); Transformation half = Power(exponent / 2, modulus); Transformation full = Multiply(half, half, modulus); if (exponent % 2) return Multiply(full, *this, modulus); else return full; } private: Transformation(const long long a00, const long long a01, const long long a10, const long long a11) : a00_(a00), a01_(a01), a10_(a10), a11_(a11) {} long long a00_; long long a01_; long long a10_; long long a11_; }; class State { public: State() : current_(0), next_(1) {} long long current() const { return current_; } State Apply( const Transformation& transformation, const long long modulus) const { return State(Add(mulmod(transformation.a00(), current_, modulus), mulmod(transformation.a01(), next_, modulus), modulus), Add(mulmod(transformation.a10(), current_, modulus), mulmod(transformation.a11(), next_, modulus), modulus)); } State Mod(const long long modulus) const { return State(current_ % modulus, next_ % modulus); } bool operator==(const State& rhs) const { return current_ == rhs.current_ && next_ == rhs.next_; } private: State(const long long current, const long long next) : current_(current), next_(next) {} long long current_; long long next_; }; bool Solve(const State& state, const Transformation& transformation, const long long remainder, const long long modulus_target, long long modulus_current, long long* solution) { if (modulus_current == modulus_target) { *solution = 0; return true; } const long long divisor = (modulus_target / modulus_current) % 2 ? 5 : 2; modulus_current *= divisor; State current = state; const State state_mod = current.Mod(modulus_current); int period = 0; while(true) { ++period; current = current.Apply(transformation, modulus_target); if (current.Mod(modulus_current) == state_mod) break; } const long long remainder_mod = remainder % modulus_current; const Transformation transformation_power = transformation.Power(period, modulus_target); current = state; for (int i = 0; i < period; ++i) { if (current.current() % modulus_current == remainder_mod && Solve(current, transformation_power, remainder, modulus_target, modulus_current, solution)) { *solution *= period; *solution += i; return true; } current = current.Apply(transformation, modulus_target); } return false; } bool Solve(const long long remainder, const long long modulus, long long* solution) { return Solve(State(), Transformation(), remainder, modulus, 1, solution); } long long Power(const long long a, long long b) { long long ret = 1; while (b--) ret *= a; return ret; } int main() { char c[kMaxLength + 1]; scanf("%s", c); long long solution; if (Solve(atoll(c), Power(10, strlen(c)), &solution)) { printf("%lld\n", kPisano + solution); } else { printf("NIE\n"); } 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 | #include <cstdio> #include <cstdlib> #include <cstring> using namespace std; const int kMaxLength = 18; const long long kPisano = 1500LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL; long long Add(long long a, long long b, long long m) { return (a + b) % m; } // http://stackoverflow.com/questions/12168348/ways-to-do-modulo-multiplication-with-primitive-types long long mulmod(long long a, long long b, long long m) { long long res = 0; while (a != 0) { if (a & 1) res = (res + b) % m; a >>= 1; b = (b << 1) % m; } return res; } class Transformation { public: Transformation() : a00_(0), a01_(1), a10_(1), a11_(1) {} long long a00() const { return a00_; } long long a01() const { return a01_; } long long a10() const { return a10_; } long long a11() const { return a11_; } static Transformation Multiply(const Transformation& a, const Transformation& b, const long long modulus) { return Transformation( Add(mulmod(a.a00(), b.a00(), modulus), mulmod(a.a01(), b.a10(), modulus), modulus), Add(mulmod(a.a00(), b.a01(), modulus), mulmod(a.a01(), b.a11(), modulus), modulus), Add(mulmod(a.a10(), b.a00(), modulus), mulmod(a.a11(), b.a10(), modulus), modulus), Add(mulmod(a.a10(), b.a01(), modulus), mulmod(a.a11(), b.a11(), modulus), modulus)); } Transformation Power(const long long exponent, const long long modulus) const { if (exponent == 0) return Transformation(1, 0, 0, 1); Transformation half = Power(exponent / 2, modulus); Transformation full = Multiply(half, half, modulus); if (exponent % 2) return Multiply(full, *this, modulus); else return full; } private: Transformation(const long long a00, const long long a01, const long long a10, const long long a11) : a00_(a00), a01_(a01), a10_(a10), a11_(a11) {} long long a00_; long long a01_; long long a10_; long long a11_; }; class State { public: State() : current_(0), next_(1) {} long long current() const { return current_; } State Apply( const Transformation& transformation, const long long modulus) const { return State(Add(mulmod(transformation.a00(), current_, modulus), mulmod(transformation.a01(), next_, modulus), modulus), Add(mulmod(transformation.a10(), current_, modulus), mulmod(transformation.a11(), next_, modulus), modulus)); } State Mod(const long long modulus) const { return State(current_ % modulus, next_ % modulus); } bool operator==(const State& rhs) const { return current_ == rhs.current_ && next_ == rhs.next_; } private: State(const long long current, const long long next) : current_(current), next_(next) {} long long current_; long long next_; }; bool Solve(const State& state, const Transformation& transformation, const long long remainder, const long long modulus_target, long long modulus_current, long long* solution) { if (modulus_current == modulus_target) { *solution = 0; return true; } const long long divisor = (modulus_target / modulus_current) % 2 ? 5 : 2; modulus_current *= divisor; State current = state; const State state_mod = current.Mod(modulus_current); int period = 0; while(true) { ++period; current = current.Apply(transformation, modulus_target); if (current.Mod(modulus_current) == state_mod) break; } const long long remainder_mod = remainder % modulus_current; const Transformation transformation_power = transformation.Power(period, modulus_target); current = state; for (int i = 0; i < period; ++i) { if (current.current() % modulus_current == remainder_mod && Solve(current, transformation_power, remainder, modulus_target, modulus_current, solution)) { *solution *= period; *solution += i; return true; } current = current.Apply(transformation, modulus_target); } return false; } bool Solve(const long long remainder, const long long modulus, long long* solution) { return Solve(State(), Transformation(), remainder, modulus, 1, solution); } long long Power(const long long a, long long b) { long long ret = 1; while (b--) ret *= a; return ret; } int main() { char c[kMaxLength + 1]; scanf("%s", c); long long solution; if (Solve(atoll(c), Power(10, strlen(c)), &solution)) { printf("%lld\n", kPisano + solution); } else { printf("NIE\n"); } return 0; } |