結果
問題 | No.187 中華風 (Hard) |
ユーザー | Tifa |
提出日時 | 2023-09-12 14:34:51 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 67 ms / 3,000 ms |
コード長 | 3,642 bytes |
コンパイル時間 | 906 ms |
コンパイル使用メモリ | 97,772 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-30 02:37:38 |
合計ジャッジ時間 | 2,434 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 3 ms
6,940 KB |
testcase_02 | AC | 55 ms
6,940 KB |
testcase_03 | AC | 56 ms
6,940 KB |
testcase_04 | AC | 67 ms
6,944 KB |
testcase_05 | AC | 66 ms
6,940 KB |
testcase_06 | AC | 67 ms
6,944 KB |
testcase_07 | AC | 66 ms
6,944 KB |
testcase_08 | AC | 47 ms
6,944 KB |
testcase_09 | AC | 47 ms
6,940 KB |
testcase_10 | AC | 48 ms
6,940 KB |
testcase_11 | AC | 65 ms
6,944 KB |
testcase_12 | AC | 66 ms
6,940 KB |
testcase_13 | AC | 13 ms
6,944 KB |
testcase_14 | AC | 12 ms
6,940 KB |
testcase_15 | AC | 53 ms
6,940 KB |
testcase_16 | AC | 54 ms
6,944 KB |
testcase_17 | AC | 2 ms
6,940 KB |
testcase_18 | AC | 2 ms
6,940 KB |
testcase_19 | AC | 2 ms
6,940 KB |
testcase_20 | AC | 50 ms
6,940 KB |
testcase_21 | AC | 2 ms
6,940 KB |
testcase_22 | AC | 66 ms
6,944 KB |
testcase_23 | AC | 2 ms
6,944 KB |
testcase_24 | AC | 1 ms
6,944 KB |
ソースコード
#line 1 "test\\yukicoder\\448.test.cpp" #include <algorithm> #define PROBLEM "https://yukicoder.me/problems/448" #line 1 "lib\\math\\crt_mod.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_mod.hpp" #line 1 "lib\\math\\inverse.hpp" #line 5 "lib\\math\\inverse.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\\inverse.hpp" namespace tifa_libs::math { constexpr u64 inverse(u64 n, u64 mod) { auto [g, x] = inv_gcd(n % mod, mod); assert(g == 1); return x; } } // namespace tifa_libs::math #line 1 "lib\\math\\safe_mod.hpp" #line 5 "lib\\math\\safe_mod.hpp" namespace tifa_libs::math { template <class T, std::enable_if_t<std::is_signed_v<T>, int> = 0> constexpr T safe_mod(T x, std::make_unsigned_t<T> mod) { return ((x %= (T)mod) < 0 ? x + (T)mod : x); } } // namespace tifa_libs::math #line 8 "lib\\math\\crt_mod.hpp" #include <numeric> #include <optional> #include <vector> namespace tifa_libs::math { inline std::optional<std::pair<u32, u32>> crt_mod(const std::vector<i32> &a, const std::vector<u32> &m, const u32 mod) { assert(a.size() == m.size()); const size_t n = a.size(); std::vector<u32> m_cpy(m); for (size_t i = 0; i < n; ++i) { u32 &mi = m_cpy[i]; for (size_t j = 0; j < i; ++j) { u32 &mj = m_cpy[j], d = std::gcd(mi, mj); if (d == 1) continue; if (safe_mod(a[i], d) != safe_mod(a[j], d)) return {}; mi /= d; mj /= d; if (u32 k = std::gcd(mi, d); k != 1) while (d % k == 0) { mi *= k; d /= k; } mj *= d; } } m_cpy.push_back(mod); std::vector<i32> pp(n + 1, 1), res(n + 1); for (size_t i = 0; i < n; ++i) { i64 u = safe_mod((safe_mod(a[i], m_cpy[i]) - res[i]) * (i64)inverse((u64)pp[i], m_cpy[i]), m_cpy[i]); for (size_t j = i + 1; j <= n; ++j) { res[j] = (i32)((res[j] + u * pp[j]) % m_cpy[j]); pp[j] = (i32)((i64)pp[j] * m_cpy[i] % m_cpy[j]); } } return std::make_pair(res.back(), pp.back()); } } // namespace tifa_libs::math #line 5 "test\\yukicoder\\448.test.cpp" #include <iostream> #line 8 "test\\yukicoder\\448.test.cpp" int main() { size_t n; std::cin >> n; std::vector<tifa_libs::i32> r(n); std::vector<tifa_libs::u32> m(n); for (size_t i = 0; i < n; ++i) std::cin >> r[i] >> m[i]; auto res = tifa_libs::math::crt_mod(r, m, 1'000'000'007); if (!res) { std::cout << "-1\n"; return 0; } std::cout << ((size_t)std::count(r.begin(), r.end(), 0) == n ? res->second : res->first) << '\n'; return 0; }