結果
問題 | No.2119 一般化百五減算 |
ユーザー | anqooqie |
提出日時 | 2022-11-05 18:46:22 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,379 bytes |
コンパイル時間 | 2,253 ms |
コンパイル使用メモリ | 214,068 KB |
実行使用メモリ | 11,832 KB |
最終ジャッジ日時 | 2024-07-19 10:50:48 |
合計ジャッジ時間 | 6,087 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
10,624 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 1 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 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | TLE | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
ソースコード
#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/inv_mod.hpp" #line 1 "/home/anqooqie/.proconlib/tools/extgcd.hpp" #line 7 "/home/anqooqie/.proconlib/tools/extgcd.hpp" namespace tools { template <typename T> ::std::tuple<T, T, T> extgcd(T prev_r, T r) { T prev_s(1); T prev_t(0); T s(0); T t(1); while (r != 0) { const T q = ::tools::quo(prev_r, r); ::std::tie(prev_r, r) = ::std::make_pair(r, prev_r - q * r); ::std::tie(prev_s, s) = ::std::make_pair(s, prev_s - q * s); ::std::tie(prev_t, t) = ::std::make_pair(t, prev_t - q * t); } if (prev_r < T(0)) prev_r = -prev_r; return ::std::make_tuple(prev_s, prev_t, prev_r); } } #line 7 "/home/anqooqie/.proconlib/tools/inv_mod.hpp" namespace tools { template <typename T1, typename T2> constexpr T2 inv_mod(const T1 x, const T2 m) { const auto [x0, y0, gcd] = ::tools::extgcd(x, m); assert(gcd == 1); return ::tools::mod(x0, m); } } #line 4 "main.cpp" // Source: https://qiita.com/drken/items/ae02240cd1f8edfc86fd // License: unknown // Author: drken namespace tools { template <typename Iterator> ::std::optional<long long> garner(const Iterator& begin, const Iterator& end, const long long upper_bound) { ::std::vector<long long> b, m; for (auto it = begin; it != end; ++it) { b.push_back(::tools::mod(it->first, it->second)); m.push_back(it->second); } ::std::vector<long long> coeffs(m.size() + 1, 1); ::std::vector<long long> constants(m.size() + 1, 0); for (::std::size_t k = 0; k < b.size(); ++k) { long long t = ::tools::mod((b[k] - constants[k]) * ::tools::inv_mod(coeffs[k], m[k]), m[k]); for (::std::size_t i = k + 1; i < m.size(); ++i) { (constants[i] += t * coeffs[i]) %= m[i]; (coeffs[i] *= m[k]) %= m[i]; } if ((constants[m.size()] += t * coeffs[m.size()]) > upper_bound) return ::std::nullopt; if ((coeffs[m.size()] *= m[k]) > upper_bound) return ::std::nullopt; } return constants.back(); } } namespace tools { template <typename Iterator> ::std::optional<long long> extended_garner(const Iterator& begin, const Iterator& end, const long long upper_bound) { ::std::vector<::std::pair<long long, long long>> v; for (auto it = begin; it != end; ++it) { v.emplace_back(::tools::mod(it->first, it->second), it->second); } for (::std::size_t i = 0; i < v.size(); ++i) { for (::std::size_t j = 0; j < i; ++j) { long long g = ::std::gcd(v[i].second, v[j].second); if ((v[i].first - v[j].first) % g != 0) return ::std::nullopt; v[i].second /= g; v[j].second /= g; long long gi = ::std::gcd(v[i].second, g); long long gj = g / gi; do { g = ::std::gcd(gi, gj); gi *= g; gj /= g; } while (g != 1); v[i].second *= gi; v[j].second *= gj; v[i].first %= v[i].second; v[j].first %= v[j].second; } } return ::tools::garner(v.begin(), v.end(), upper_bound); } } using ll = long long; 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>> v(M); for (auto& [C, B] : v) std::cin >> B >> C; if (const auto answer = tools::extended_garner(v.begin(), v.end(), N); answer) { std::cout << *answer << '\n'; } else { std::cout << "NaN" << '\n'; } return 0; }