結果
問題 | No.187 中華風 (Hard) |
ユーザー | Tifa |
提出日時 | 2023-09-12 02:00:00 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,585 bytes |
コンパイル時間 | 853 ms |
コンパイル使用メモリ | 85,632 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-29 15:09:00 |
合計ジャッジ時間 | 1,816 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 3 ms
5,376 KB |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
ソースコード
#line 1 "test\\yukicoder\\448.test.cpp" #define PROBLEM "https://yukicoder.me/problems/448" #line 1 "lib\\math\\crt.hpp" #line 1 "lib\\util.hpp" #include <cassert> #include <cstddef> #include <cstdint> #include <type_traits> namespace tifa_libs { using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; using i128 = __int128_t; using u128 = __uint128_t; } // namespace tifa_libs #line 5 "lib\\math\\crt.hpp" #line 1 "lib\\math\\inv_gcd.hpp" #line 5 "lib\\math\\inv_gcd.hpp" #line 1 "lib\\math\\exgcd.hpp" #line 5 "lib\\math\\exgcd.hpp" #include <tuple> namespace tifa_libs::math { // @return tuple(g, x, y) s.t. g = gcd(a, b), xa + yb = g, |x| + |y| is the minimal (primary) and x <= y (secondarily) constexpr std::tuple<u64, i64, i64> exgcd(i64 a, i64 b) { i64 x1 = 1, x2 = 0, x3 = 0, x4 = 1; while (b) { i64 c = a / b; std::tie(x1, x2, x3, x4, a, b) = std::make_tuple(x3, x4, x1 - x3 * c, x2 - x4 * c, b, a - b * c); } return {a, x1, x2}; } } // namespace tifa_libs::math #line 7 "lib\\math\\inv_gcd.hpp" namespace tifa_libs::math { constexpr std::pair<u64, u64> inv_gcd(u64 n, u64 mod) { auto [g, x, y] = exgcd((i64)(n % mod), (i64)mod); return {g, x > 0 ? (u64)x : (u64)(x % (i64)mod + (i64)mod) % mod}; } } // namespace tifa_libs::math #line 7 "lib\\math\\crt.hpp" #include <vector> namespace tifa_libs::math { // solve x == r_i (mod m_i) // @param lcm(m) < INT64_MAX // @return {x, lcm(m)} inline std::pair<u64, u64> crt(const std::vector<u64> &r, const std::vector<u64> &m) { assert(r.size() == m.size()); size_t n = r.size(); u64 r0 = 0, m0 = 1; for (size_t i = 0; i < n; i++) { assert(m[i]); u64 r1 = r[i] % m[i], m1 = m[i]; if (m0 < m1) { std::swap(r0, r1); std::swap(m0, m1); } if (m0 % m1 == 0) { if (r0 % m1 != r1) return {0, 0}; continue; } auto [g, im] = inv_gcd(m0, m1); u64 u1 = (m1 / g); if ((r1 - r0) % g) return {0, 0}; u64 x = (r1 - r0) / g % u1 * im % u1; r0 += x * m0; m0 *= u1; } return {r0, m0}; } } // namespace tifa_libs::math #line 4 "test\\yukicoder\\448.test.cpp" #include <iostream> #line 7 "test\\yukicoder\\448.test.cpp" int main() { tifa_libs::i64 n; std::cin >> n; std::vector<tifa_libs::u64> r, m; r.reserve((size_t)n); m.reserve((size_t)n); while (n--) { tifa_libs::u64 x, y; std::cin >> x >> y; r.push_back(x); m.push_back(y); } auto [R, M] = tifa_libs::math::crt(r, m); std::cout << (M ? (tifa_libs::i64)R : -1) << '\n'; return 0; }