結果
問題 | No.2119 一般化百五減算 |
ユーザー | anqooqie |
提出日時 | 2022-11-05 20:04:44 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 25,792 bytes |
コンパイル時間 | 2,475 ms |
コンパイル使用メモリ | 219,420 KB |
実行使用メモリ | 5,760 KB |
最終ジャッジ日時 | 2024-07-19 11:47:31 |
合計ジャッジ時間 | 3,291 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 3 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 2 ms
5,376 KB |
testcase_14 | AC | 2 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 24 ms
5,376 KB |
testcase_21 | AC | 23 ms
5,376 KB |
testcase_22 | AC | 30 ms
5,632 KB |
testcase_23 | AC | 28 ms
5,760 KB |
testcase_24 | AC | 30 ms
5,632 KB |
コンパイルメッセージ
/home/anqooqie/.proconlib/tools/safe_int.hpp: In function 'constexpr tools::safe_int<T> tools::operator-(const safe_int<T>&, const safe_int<T>&)': /home/anqooqie/.proconlib/tools/safe_int.hpp:182:13: warning: expected 'template' keyword before dependent template name [-Wmissing-template-keyword]
ソースコード
#line 1 "main.cpp" #include <bits/stdc++.h> #line 1 "/home/anqooqie/.proconlib/tools/mod.hpp" #include <type_traits> #line 1 "/home/anqooqie/.proconlib/tools/quo.hpp" #line 5 "/home/anqooqie/.proconlib/tools/quo.hpp" namespace tools { template <typename M, typename N> constexpr ::std::common_type_t<M, N> quo(const M lhs, const N rhs) { if (lhs >= 0) { return lhs / rhs; } else { if (rhs >= 0) { return -((-lhs - 1 + rhs) / rhs); } else { return (-lhs - 1 + -rhs) / -rhs; } } } } #line 6 "/home/anqooqie/.proconlib/tools/mod.hpp" namespace tools { template <typename M, typename N> constexpr ::std::common_type_t<M, N> mod(const M lhs, const N rhs) { if constexpr (::std::is_unsigned_v<M> && ::std::is_unsigned_v<N>) { return lhs % rhs; } else { return lhs - ::tools::quo(lhs, rhs) * rhs; } } } #line 1 "/home/anqooqie/.proconlib/tools/safe_int.hpp" #line 9 "/home/anqooqie/.proconlib/tools/safe_int.hpp" #include <optional> namespace tools { template <typename T, typename = void> class safe_int; template <typename T> class safe_int<T, ::std::enable_if_t<::std::is_signed_v<T>>> { private: enum class type { finite, pos_inf, neg_inf, nan }; typename ::tools::safe_int<T>::type m_type; T m_value; constexpr safe_int(const typename ::tools::safe_int<T>::type type) : m_type(type), m_value(T()) { } public: constexpr safe_int() : m_type(::tools::safe_int<T>::type::finite), m_value(T()) { } explicit constexpr safe_int(const T value) : m_type(::tools::safe_int<T>::type::finite), m_value(value) { } constexpr safe_int(const ::tools::safe_int<T>& other) : m_type(other.m_type), m_value(other.m_value) { } ~safe_int() = default; constexpr ::tools::safe_int<T>& operator=(const ::tools::safe_int<T>& other) { this->m_type = other.m_type; this->m_value = other.m_value; return *this; } static constexpr ::tools::safe_int<T> infinity() { return tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf); } static constexpr ::tools::safe_int<T> nan() { return tools::safe_int<T>(::tools::safe_int<T>::type::nan); } private: static constexpr int f1(const ::tools::safe_int<T>& n) { switch (n.m_type) { case ::tools::safe_int<T>::type::neg_inf: return 0; case ::tools::safe_int<T>::type::finite: return 1; case ::tools::safe_int<T>::type::pos_inf: return 2; default: // nan return 3; } }; static constexpr int f2(const ::tools::safe_int<T>& n) { switch (n.m_type) { case ::tools::safe_int<T>::type::neg_inf: return 0; case ::tools::safe_int<T>::type::finite: if (n.m_value < 0) { return 1; } else if (n.m_value == 0) { return 2; } else { return 3; } case ::tools::safe_int<T>::type::pos_inf: return 4; default: // nan return 5; } }; static constexpr ::std::optional<::tools::safe_int<T>> Q() { return ::std::nullopt; } static constexpr ::std::optional<::tools::safe_int<T>> Z() { return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(0)); } static constexpr ::std::optional<::tools::safe_int<T>> N() { return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::neg_inf)); } static constexpr ::std::optional<::tools::safe_int<T>> P() { return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf)); } static constexpr ::std::optional<::tools::safe_int<T>> U() { return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::nan)); } static constexpr ::std::optional<bool> BQ() { return ::std::nullopt; } static constexpr ::std::optional<bool> BF() { return ::std::optional<bool>(false); } static constexpr ::std::optional<bool> BT() { return ::std::optional<bool>(true); } public: constexpr bool is_finite() const { return this->m_type == ::tools::safe_int<T>::type::finite; } constexpr bool is_nan() const { return this->m_type == ::tools::safe_int<T>::type::nan; } constexpr T val() const { assert(this->is_finite()); return this->m_value; } friend constexpr bool operator==(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 4>, 4>({{ {BT(), BF(), BF(), BF()}, {BF(), BQ(), BF(), BF()}, {BF(), BF(), BT(), BF()}, {BF(), BF(), BF(), BF()} }}); if (const auto r = table[f1(x)][f1(y)]; r) return *r; return x.m_value == y.m_value; } friend constexpr bool operator!=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { return !(x == y); } constexpr ::tools::safe_int<T> operator+() const { return *this; } constexpr ::tools::safe_int<T> operator-() const { constexpr auto table = ::std::array<::std::optional<::tools::safe_int<T>>, 4>({ {P(), Q(), N(), U()} }); if (const auto r = table[f1(*this)]; r) return *r; if (this->m_value == ::std::numeric_limits<T>::min()) return *U(); return ::tools::safe_int<T>(-this->m_value); } friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{ {N(), N(), U(), U()}, {N(), Q(), P(), U()}, {U(), P(), P(), U()}, {U(), U(), U(), U()} }}); if (const auto r = table[f1(x)][f1(y)]; r) return *r; if (y.m_value > 0 && x.m_value > ::std::numeric_limits<T>::max() - y.m_value) return *U(); if (y.m_value < 0 && x.m_value < ::std::numeric_limits<T>::min() - y.m_value) return *U(); return ::tools::safe_int<T>(x.m_value + y.m_value); } friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const T& y) { return x + tools::safe_int<T>(y); } friend constexpr ::tools::safe_int<T> operator+(const T& x, const ::tools::safe_int<T>& y) { return tools::safe_int<T>(x) + y; } friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{ {U(), N(), N(), U()}, {P(), Q(), N(), U()}, {P(), P(), U(), U()}, {U(), U(), U(), U()} }}); if (const auto r = table[f1(x)][f1(y)]; r) return *r; if (y.m_value < 0 && x.m_value > ::std::numeric_limits<T>::max() + y.m_value) return *U(); if (y.m_value > 0 && x.m_value < ::std::numeric_limits<T>::min() + y.m_value) return *U(); return ::tools::safe_int<T>(x.m_value - y.m_value); } friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const T& y) { return x - tools::safe_int<T>(y); } friend constexpr ::tools::safe_int<T> operator-(const T& x, const ::tools::safe_int<T>& y) { return tools::safe_int<T>(x) - y; } friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 6>, 6>({{ {P(), P(), U(), N(), N(), U()}, {P(), Q(), Z(), Q(), N(), U()}, {U(), Z(), Z(), Z(), U(), U()}, {N(), Q(), Z(), Q(), P(), U()}, {N(), N(), U(), P(), P(), U()}, {U(), U(), U(), U(), U(), U()} }}); if (const auto r = table[f2(x)][f2(y)]; r) return *r; if (x.m_value > 0) { if (y.m_value > 0) { if (x.m_value > ::std::numeric_limits<T>::max() / y.m_value) { return *U(); } } else { if (y.m_value < ::std::numeric_limits<T>::min() / x.m_value) { return *U(); } } } else { if (y.m_value > 0) { if (x.m_value < ::std::numeric_limits<T>::min() / y.m_value) { return *U(); } } else { if (x.m_value != 0 && y.m_value < ::std::numeric_limits<T>::max() / x.m_value) { return *U(); } } } return ::tools::safe_int<T>(x.m_value * y.m_value); } friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const T& y) { return x * tools::safe_int<T>(y); } friend constexpr ::tools::safe_int<T> operator*(const T& x, const ::tools::safe_int<T>& y) { return tools::safe_int<T>(x) * y; } friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 6>, 6>({{ {U(), P(), U(), N(), U(), U()}, {Z(), Q(), U(), Q(), Z(), U()}, {Z(), Z(), U(), Z(), Z(), U()}, {Z(), Q(), U(), Q(), Z(), U()}, {U(), N(), U(), P(), U(), U()}, {U(), U(), U(), U(), U(), U()} }}); if (const auto r = table[f2(x)][f2(y)]; r) return *r; if (x.m_value == ::std::numeric_limits<T>::min() && y.m_value == -1) return *U(); return ::tools::safe_int<T>(x.m_value / y.m_value); } friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const T& y) { return x / tools::safe_int<T>(y); } friend constexpr ::tools::safe_int<T> operator/(const T& x, const ::tools::safe_int<T>& y) { return tools::safe_int<T>(x) / y; } friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 6>, 6>({{ {U(), U(), U(), U(), U(), U()}, {U(), Q(), U(), Q(), U(), U()}, {U(), Z(), U(), Z(), U(), U()}, {U(), Q(), U(), Q(), U(), U()}, {U(), U(), U(), U(), U(), U()}, {U(), U(), U(), U(), U(), U()} }}); if (const auto r = table[f2(x)][f2(y)]; r) return *r; if (x.m_value == ::std::numeric_limits<T>::min() && y.m_value == -1) return *U(); return ::tools::safe_int<T>(x.m_value % y.m_value); } friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const T& y) { return x % tools::safe_int<T>(y); } friend constexpr ::tools::safe_int<T> operator%(const T& x, const ::tools::safe_int<T>& y) { return tools::safe_int<T>(x) % y; } constexpr ::tools::safe_int<T>& operator+=(const ::tools::safe_int<T>& other) { return *this = *this + other; } constexpr ::tools::safe_int<T>& operator+=(const T& other) { return *this = *this + ::tools::safe_int<T>(other); } constexpr ::tools::safe_int<T>& operator-=(const ::tools::safe_int<T>& other) { return *this = *this - other; } constexpr ::tools::safe_int<T>& operator-=(const T& other) { return *this = *this - ::tools::safe_int<T>(other); } constexpr ::tools::safe_int<T>& operator*=(const ::tools::safe_int<T>& other) { return *this = *this * other; } constexpr ::tools::safe_int<T>& operator*=(const T& other) { return *this = *this * ::tools::safe_int<T>(other); } constexpr ::tools::safe_int<T>& operator/=(const ::tools::safe_int<T>& other) { return *this = *this / other; } constexpr ::tools::safe_int<T>& operator/=(const T& other) { return *this = *this / ::tools::safe_int<T>(other); } constexpr ::tools::safe_int<T>& operator%=(const ::tools::safe_int<T>& other) { return *this = *this % other; } constexpr ::tools::safe_int<T>& operator%=(const T& other) { return *this = *this % ::tools::safe_int<T>(other); } friend constexpr bool operator<(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 4>, 4>({{ {BF(), BT(), BT(), BF()}, {BF(), BQ(), BT(), BF()}, {BF(), BF(), BF(), BF()}, {BF(), BF(), BF(), BF()} }}); if (const auto r = table[f1(x)][f1(y)]; r) return *r; return x.m_value < y.m_value; } friend constexpr bool operator>(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 4>, 4>({{ {BF(), BF(), BF(), BF()}, {BT(), BQ(), BF(), BF()}, {BT(), BT(), BF(), BF()}, {BF(), BF(), BF(), BF()} }}); if (const auto r = table[f1(x)][f1(y)]; r) return *r; return x.m_value > y.m_value; } friend constexpr bool operator<=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { return x < y || x == y; } friend constexpr bool operator>=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { return x > y || x == y; } }; template <typename T> class safe_int<T, ::std::enable_if_t<::std::is_unsigned_v<T>>> { private: enum class type { finite, pos_inf, nan }; typename ::tools::safe_int<T>::type m_type; T m_value; constexpr safe_int(const typename ::tools::safe_int<T>::type type) : m_type(type), m_value(T()) { } public: constexpr safe_int() : m_type(::tools::safe_int<T>::type::finite), m_value(T()) { } explicit constexpr safe_int(const T value) : m_type(::tools::safe_int<T>::type::finite), m_value(value) { } constexpr safe_int(const ::tools::safe_int<T>& other) : m_type(other.m_type), m_value(other.m_value) { } ~safe_int() = default; constexpr ::tools::safe_int<T>& operator=(const ::tools::safe_int<T>& other) { this->m_type = other.m_type; this->m_value = other.m_value; return *this; } static constexpr ::tools::safe_int<T> infinity() { return tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf); } static constexpr ::tools::safe_int<T> nan() { return tools::safe_int<T>(::tools::safe_int<T>::type::nan); } private: static constexpr int f1(const ::tools::safe_int<T>& n) { switch (n.m_type) { case ::tools::safe_int<T>::type::finite: return 0; case ::tools::safe_int<T>::type::pos_inf: return 1; default: // nan return 2; } }; static constexpr int f2(const ::tools::safe_int<T>& n) { switch (n.m_type) { case ::tools::safe_int<T>::type::finite: if (n.m_value == 0) { return 0; } else { return 1; } case ::tools::safe_int<T>::type::pos_inf: return 2; default: // nan return 3; } }; static constexpr ::std::optional<::tools::safe_int<T>> Q() { return ::std::nullopt; } static constexpr ::std::optional<::tools::safe_int<T>> Z() { return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(0)); } static constexpr ::std::optional<::tools::safe_int<T>> P() { return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::pos_inf)); } static constexpr ::std::optional<::tools::safe_int<T>> U() { return ::std::optional<::tools::safe_int<T>>(::tools::safe_int<T>(::tools::safe_int<T>::type::nan)); } static constexpr ::std::optional<bool> BQ() { return ::std::nullopt; } static constexpr ::std::optional<bool> BF() { return ::std::optional<bool>(false); } static constexpr ::std::optional<bool> BT() { return ::std::optional<bool>(true); } public: constexpr bool is_finite() const { return this->m_type == ::tools::safe_int<T>::type::finite; } constexpr bool is_nan() const { return this->m_type == ::tools::safe_int<T>::type::nan; } constexpr T val() const { assert(this->is_finite()); return this->m_value; } friend constexpr bool operator==(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 3>, 3>({{ {BQ(), BF(), BF()}, {BF(), BT(), BF()}, {BF(), BF(), BF()} }}); if (const auto r = table[f1(x)][f1(y)]; r) return *r; return x.m_value == y.m_value; } friend constexpr bool operator!=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { return !(x == y); } constexpr ::tools::safe_int<T> operator+() const { return *this; } constexpr ::tools::safe_int<T> operator-() const { constexpr auto table = ::std::array<::std::optional<::tools::safe_int<T>>, 3>({ {Q(), U(), U()} }); if (const auto r = table[f1(*this)]; r) return *r; if (this->m_value > 0) return *U(); return ::tools::safe_int<T>(0); } friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 3>, 3>({{ {Q(), P(), U()}, {P(), P(), U()}, {U(), U(), U()} }}); if (const auto r = table[f1(x)][f1(y)]; r) return *r; if (y.m_value > 0 && x.m_value > ::std::numeric_limits<T>::max() - y.m_value) return *U(); return ::tools::safe_int<T>(x.m_value + y.m_value); } friend constexpr ::tools::safe_int<T> operator+(const ::tools::safe_int<T>& x, const T& y) { return x + tools::safe_int<T>(y); } friend constexpr ::tools::safe_int<T> operator+(const T& x, const ::tools::safe_int<T>& y) { return tools::safe_int<T>(x) + y; } friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 3>, 3>({{ {Q(), U(), U()}, {P(), U(), U()}, {U(), U(), U()} }}); if (const auto r = table[f1(x)][f1(y)]; r) return *r; if (x.m_value < y.m_value) return *U(); return ::tools::safe_int<T>(x.m_value - y.m_value); } friend constexpr ::tools::safe_int<T> operator-(const ::tools::safe_int<T>& x, const T& y) { return x - tools::safe_int<T>(y); } friend constexpr ::tools::safe_int<T> operator-(const T& x, const ::tools::safe_int<T>& y) { return tools::safe_int<T>(x) - y; } friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{ {Z(), Z(), U(), U()}, {Z(), Q(), P(), U()}, {U(), P(), P(), U()}, {U(), U(), U(), U()} }}); if (const auto r = table[f2(x)][f2(y)]; r) return *r; if (x.m_value > ::std::numeric_limits<T>::max() / y.m_value) { return *U(); } return ::tools::safe_int<T>(x.m_value * y.m_value); } friend constexpr ::tools::safe_int<T> operator*(const ::tools::safe_int<T>& x, const T& y) { return x * tools::safe_int<T>(y); } friend constexpr ::tools::safe_int<T> operator*(const T& x, const ::tools::safe_int<T>& y) { return tools::safe_int<T>(x) * y; } friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{ {U(), Z(), Z(), U()}, {U(), Q(), Z(), U()}, {U(), P(), U(), U()}, {U(), U(), U(), U()} }}); if (const auto r = table[f2(x)][f2(y)]; r) return *r; return ::tools::safe_int<T>(x.m_value / y.m_value); } friend constexpr ::tools::safe_int<T> operator/(const ::tools::safe_int<T>& x, const T& y) { return x / tools::safe_int<T>(y); } friend constexpr ::tools::safe_int<T> operator/(const T& x, const ::tools::safe_int<T>& y) { return tools::safe_int<T>(x) / y; } friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<::tools::safe_int<T>>, 4>, 4>({{ {U(), Z(), U(), U()}, {U(), Q(), U(), U()}, {U(), U(), U(), U()}, {U(), U(), U(), U()} }}); if (const auto r = table[f2(x)][f2(y)]; r) return *r; return ::tools::safe_int<T>(x.m_value % y.m_value); } friend constexpr ::tools::safe_int<T> operator%(const ::tools::safe_int<T>& x, const T& y) { return x % tools::safe_int<T>(y); } friend constexpr ::tools::safe_int<T> operator%(const T& x, const ::tools::safe_int<T>& y) { return tools::safe_int<T>(x) % y; } constexpr ::tools::safe_int<T>& operator+=(const ::tools::safe_int<T>& other) { return *this = *this + other; } constexpr ::tools::safe_int<T>& operator+=(const T& other) { return *this = *this + ::tools::safe_int<T>(other); } constexpr ::tools::safe_int<T>& operator-=(const ::tools::safe_int<T>& other) { return *this = *this - other; } constexpr ::tools::safe_int<T>& operator-=(const T& other) { return *this = *this - ::tools::safe_int<T>(other); } constexpr ::tools::safe_int<T>& operator*=(const ::tools::safe_int<T>& other) { return *this = *this * other; } constexpr ::tools::safe_int<T>& operator*=(const T& other) { return *this = *this * ::tools::safe_int<T>(other); } constexpr ::tools::safe_int<T>& operator/=(const ::tools::safe_int<T>& other) { return *this = *this / other; } constexpr ::tools::safe_int<T>& operator/=(const T& other) { return *this = *this / ::tools::safe_int<T>(other); } constexpr ::tools::safe_int<T>& operator%=(const ::tools::safe_int<T>& other) { return *this = *this % other; } constexpr ::tools::safe_int<T>& operator%=(const T& other) { return *this = *this % ::tools::safe_int<T>(other); } friend constexpr bool operator<(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 3>, 3>({{ {BQ(), BT(), BF()}, {BF(), BF(), BF()}, {BF(), BF(), BF()} }}); if (const auto r = table[f1(x)][f1(y)]; r) return *r; return x.m_value < y.m_value; } friend constexpr bool operator>(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { constexpr auto table = ::std::array<::std::array<::std::optional<bool>, 3>, 3>({{ {BQ(), BF(), BF()}, {BT(), BF(), BF()}, {BF(), BF(), BF()} }}); if (const auto r = table[f1(x)][f1(y)]; r) return *r; return x.m_value > y.m_value; } friend constexpr bool operator<=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { return x < y || x == y; } friend constexpr bool operator>=(const ::tools::safe_int<T>& x, const ::tools::safe_int<T>& y) { return x > y || x == y; } }; } #line 1 "/home/anqooqie/.proconlib/tools/greater_by_second.hpp" #line 5 "/home/anqooqie/.proconlib/tools/greater_by_second.hpp" namespace tools { class greater_by_second { public: template <class T1, class T2> bool operator()(const ::std::pair<T1, T2>& x, const ::std::pair<T1, T2>& y) const { return x.second > y.second; } }; } #line 1 "/home/anqooqie/.proconlib/tools/less_by_first.hpp" #line 5 "/home/anqooqie/.proconlib/tools/less_by_first.hpp" namespace tools { class less_by_first { public: template <class T1, class T2> bool operator()(const ::std::pair<T1, T2>& x, const ::std::pair<T1, T2>& y) const { return x.first < y.first; } }; } #line 6 "main.cpp" using ll = long long; using s = tools::safe_int<ll>; int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); ll N, M; std::cin >> N >> M; std::vector<std::pair<ll, ll>> eqns(M); for (auto& [C, B] : eqns) { std::cin >> B >> C; C = tools::mod(C, B); } std::sort(eqns.begin(), eqns.end(), tools::greater_by_second()); ll vl = 0; for (ll vr = 0, al = 0, ar = 0; al < M; vl = vr, al = ar) { for (; ar < M && eqns[al] == eqns[ar]; ++vr, ++ar); if (vl < al) std::move(eqns.begin() + al, eqns.begin() + ar, eqns.begin() + vl); const auto [min, max] = std::minmax_element(eqns.begin() + vl, eqns.begin() + vr, tools::less_by_first()); if (min->first < max->first) { std::cout << "NaN" << '\n'; return 0; } vr = vl + 1; } eqns.erase(eqns.begin() + vl, eqns.end()); auto lcm = std::accumulate(eqns.begin(), eqns.end(), s(1), [](const auto& lcm, const auto& eqn) { return lcm * eqn.second; }); if (lcm.is_nan()) lcm = s::infinity(); std::vector<ll> possible_answers(std::min(s(N + 1), lcm).val()); std::iota(possible_answers.begin(), possible_answers.end(), 0); for (const auto& [C, B] : eqns) { possible_answers.erase(std::remove_if(possible_answers.begin(), possible_answers.end(), [&](const auto possible_answer) { return possible_answer % B != C; }), possible_answers.end()); } if (!possible_answers.empty()) { std::cout << possible_answers.front() << '\n'; } else { std::cout << "NaN" << '\n'; } return 0; }