verify/yukicoder/186.test.cpp

• View this file on GitHub
• Last update: 2024-11-09 02:03:28+09:00
• Problem: https://yukicoder.me/problems/no/186

Depends on

• chinese_remainder_theorem (src/math/chinese_remainder_theorem.hpp)
• inv_gcd (src/math/inv_gcd.hpp)
• template (src/template/template.hpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/186"
#include "../../src/template/template.hpp"
#include "../../src/math/chinese_remainder_theorem.hpp"
int main(void) {
    vector<ll> x(3), y(3);
    rep(i, 0, 3) cin >> x[i] >> y[i];
    P ans = chinese_remainder_theorem(x, y);
    if(ans == P(0, 0)) {
        cout << -1 << '\n';
    } else {
        if(ans.first == 0) ans.first = ans.second;
        cout << ans.first << '\n';
    }
}

#line 1 "verify/yukicoder/186.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/186"
#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/math/inv_gcd.hpp"
constexpr pair<long long, long long> inv_gcd(long long a, const long long b) {
    a %= b;
    if(a < 0) a += b;
    if(a == 0) return {b, 0};
    long long s = b, t = a, m0 = 0, m1 = 1;
    while(t) {
        const long long u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        long long tmp = s;
        s = t;
        t = tmp;
        tmp = m0;
        m0 = m1;
        m1 = tmp;
    }
    if(m0 < 0) m0 += b / s;
    return {s, m0};
}
#line 4 "src/math/chinese_remainder_theorem.hpp"
pair<long long, long long> chinese_remainder_theorem(const vector<long long>& r, const vector<long long>& m) {
    assert(r.size() == m.size());
    const int n = (int)r.size();
    long long r0 = 0, m0 = 1;
    for(int i = 0; i < n; ++i) {
        assert(m[i] >= 1);
        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 {0, 0};
            continue;
        }
        const auto [g, im] = inv_gcd(m0, m1);
        const long long u1 = m1 / g;
        if((r1 - r0) % g) return {0, 0};
        const long long x = (r1 - r0) / g % u1 * im % u1;
        r0 += x * m0;
        m0 *= u1;
        if(r0 < 0) r0 += m0;
    }
    return {r0, m0};
}
#line 4 "verify/yukicoder/186.test.cpp"
int main(void) {
    vector<ll> x(3), y(3);
    rep(i, 0, 3) cin >> x[i] >> y[i];
    P ans = chinese_remainder_theorem(x, y);
    if(ans == P(0, 0)) {
        cout << -1 << '\n';
    } else {
        if(ans.first == 0) ans.first = ans.second;
        cout << ans.first << '\n';
    }
}

Back to top page