#line 1 "test/math/crt/yuki447.test.cpp" #define PROBLEM "https://yukicoder.me/problems/447" #line 2 "src/Template.hpp" #define CUT #include using namespace std; #define rep(i, l, r) for (int i = (l); i < (r); ++i) #define rrep(i, l, r) for (int i = (r); i --> (l);) #define all(c) begin(c), end(c) #ifdef LOCAL #define debug(...) debug_impl(#__VA_ARGS__, __VA_ARGS__) template void debug_impl(string s, H&& h, Ts&&... ts) { cerr << '(' << s << "): (" << forward(h); ((cerr << ", " << forward(ts)), ..., (cerr << ")\n")); } #else #define debug(...) void(0) #endif template bool chmax(T& a, const T& b) { return b > a ? (a = b, true) : false; } template bool chmin(T& a, const T& b) { return b < a ? (a = b, true) : false; } template istream& operator>>(istream& in, vector& v) { for (auto& e : v) in >> e; return in; } template void read(Args&... args) { (cin >> ... >> args); } template ostream& operator<<(ostream& out, const vector& v) { int n = v.size(); rep(i, 0, n) { out << v[i]; if (i + 1 != n) out << ' '; } return out; } template void print(H&& h, Ts &&... ts) { cout << h, ((cout << ' ' << forward(ts)), ..., (cout << '\n')); } struct io_setup_ { io_setup_() { ios::sync_with_stdio(false), cin.tie(nullptr); cout << fixed << setprecision(10); } } io_setup{}; #undef CUT #define NOTE compile command: \texttt{g++ -std=gnu++17 -Wall -Wextra -g -fsanitize=address -fsanitize=undefined \$\{file\} -o \$\{fileDirname\}/\$\{fileBasenameNoExtension\}} #undef NOTE #define NOTE \texttt{-DLOCAL} を加えると \texttt{debug(...)} による出力が有効となる #undef NOTE #line 3 "src/math/CRT.hpp" #define CUT #line 3 "src/math/ExtGCD.hpp" #define CUT constexpr long safe_mod(long long x, long long m) { return (x %= m) < 0 ? x + m : x; } // Returns `(x,g)` s.t. `g=\gcd(a,b)`, `xa\equiv g \pmod{b}`, and `0\leq x< \frac{b}{g}` constexpr pair inv_gcd(long long a, long long b) { assert(b > 0); a = safe_mod(a, b); if (a == 0) return { 0, b }; long long s = b, t = a, x = 0, y = 1; while (t) { long long u = s / t; s -= t * u, swap(s, t); x -= y * u, swap(x, y); } if (x < 0) x += b / s; return { x, s }; } // Returns `x` s.t. `xa\equiv 1 \pmod{m}`. // Requirement: `\gcd(a, m) = 1`. constexpr long long inv_mod(long long a, long long m) { auto [x, g] = inv_gcd(a, m); assert(g == 1); return x; } // Returns `(x_0,y_0,g)` s.t. `g=\gcd(a,b)`, `ax_0 + by_0 = g`, and `0\leq x_0<\frac{b}{g}`. // 一般解は `(x,y)=(x_0+k\cdot\dfrac{b}{g}, y_0-k\cdot\dfrac{a}{g})\;(k\in\mathbb{Z})` なので、`(x_0,y_0)` は `x` が非負の下で最小の解 constexpr tuple ext_gcd(long long a, long long b) { auto [x, g] = inv_gcd(a, b); return { x, (g - x * a) / b, g }; } #undef CUT #line 5 "src/math/CRT.hpp" // Returns the pair `(x, M)` s.t. `\forall i.\; x \equiv r_i \pmod{m_i}` and `M = \mathrm{lcm}(m_1,\ldots,m_k)`. // If such `x` doesn't exists, then returns `(-1,-1)` pair crt(vector r, vector m) { assert(r.size() == m.size()); int n = r.size(); long long r0 = 0, m0 = 1; for (int i = 0; i < n; i++) { assert(1 <= m[i]); long long r1 = r[i] % m[i], m1 = m[i]; if (r1 < 0) r1 += m[i]; if (m0 < m1) swap(r0, r1), swap(m0, m1); if (m0 % m1 == 0) { if (r0 % m1 != r1) return { -1, -1 }; continue; } auto [im, g] = inv_gcd(m0, m1); long long u1 = (m1 / g); if ((r1 - r0) % g) return { -1, -1 }; long long x = (r1 - r0) / g % u1 * im % u1; r0 += x * m0; m0 *= u1; if (r0 < 0) r0 += m0; } return { r0, m0 }; } #undef CUT #line 4 "test/math/crt/yuki447.test.cpp" int main() { vector r(3), m(3); rep(i, 0, 3) { read(r[i], m[i]); } print(crt(r, m).first); }