結果
問題 |
No.2558 中国剰余定理
|
ユーザー |
|
提出日時 | 2023-12-02 14:48:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 2,493 bytes |
コンパイル時間 | 3,872 ms |
コンパイル使用メモリ | 249,900 KB |
最終ジャッジ日時 | 2025-02-18 03:58:06 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#include <bits/stdc++.h> #include <bits/extc++.h> using i64 = long long; namespace internal { template <typename T> T safe_mod(T x, T m) { x %= m; if (x < 0) x += m; return x; } template <typename T> T pow_mod(T x, T n, T m) { assert(0 <= n && 1 <= m); if (m == 1) return 0; T r = 1, y = safe_mod(x, m); while (n) { if (n & 1) r = (r % y) % m; y = (y * y) % m; n >>= 1; } return r; } template <typename T> std::pair<T, T> inv_gcd(T a, T b) { a = safe_mod(a, b); if (a == 0) return {b, 0}; T s = b, t = a; T m0 = 0, m1 = 1; while (t) { T u = s / t; s -= t * u; m0 -= m1 * u; auto tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp; } if (m0 < 0) m0 += b / s; return {s, m0}; } template <typename T> T inv_mod(T x, T m) { assert(1 <= m); auto z = inv_gcd(x, m); assert(z.first == 1); return z.second; } //(rem,mod) template <typename T> std::pair<T, T> crt(const std::vector<T> &r, const std::vector<T> &m) { assert(r.size() == m.size()); int n = (int)r.size(); T r0 = 0, m0 = 1; for (int i = 0; i < n; i++) { assert(1 <= m[i]); T r1 = safe_mod(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; } T g, im; std::tie(g, im) = inv_gcd(m0, m1); T u1 = m1 / g; if ((r1 - r0) % g) return {0, 0}; long long x = (r1 - r0) / g % u1 * im % u1; r0 += x * m0; m0 *= u1; if (r0 < 0) r0 += m0; } return {r0, m0}; } } void solve() { int A, B, a, b; std::cin >> A >> B >> a >> b; auto crt = internal::crt<int>({a, b}, {A, B}); std::cout << crt.first << '\n'; } int main() { std::cin.tie(nullptr)->sync_with_stdio(false); solve(); return 0; }