verify/yukicoder-2117.test.cpp

• View this file on GitHub
• Last update: 2026-06-05 17:58:28+09:00
• Problem: https://yukicoder.me/problems/no/2117

Depends on

• $A_i x\equiv B_i\pmod{M_i}$ の形の連立合同方程式 (math/number-theory/generalized-garner.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/2117

#include <iostream>
#include <vector>

#include "../math/number-theory/generalized-garner.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    long long b0, c0, b1, c1;
    std::cin >> b0 >> c0;
    std::cin >> b1 >> c1;
    const std::vector<long long> a = {1, 1};
    const std::vector<long long> b = {c0, c1};
    const std::vector<long long> m = {b0, b1};
    const auto [r, mod] = generalized_garner<long long>(a, b, m);
    if (mod == 0) {
        std::cout << "NaN\n";
    } else {
        std::cout << r << '\n';
    }
    return 0;
}

#line 1 "verify/yukicoder-2117.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/2117

#include <iostream>
#include <vector>

#line 1 "math/number-theory/generalized-garner.hpp"



// A_i x ≡ B_i (mod M_i) の形の連立合同方程式を解く。
// 各式を x ≡ r_i (mod m_i) に直してから一般の中国剰余定理で合成する。
// M_i > 0、a, b, m のサイズ一致、返り値が R1, R2 に収まることを仮定する。
// 係数や法は互いに素でなくてよい。解なしなら (0, 0) を返す。
// 標準 64 ビット整数型では計算量 O(N log max M_i)。
// __int128 では剰余乗算をダブリングで行う。

#include <cassert>
#include <type_traits>
#include <utility>
#line 15 "math/number-theory/generalized-garner.hpp"

namespace generalized_garner_internal {
template <typename T> struct is_integral : std::is_integral<T> {};

#ifdef __SIZEOF_INT128__
template <> struct is_integral<__int128_t> : std::true_type {};
template <> struct is_integral<__uint128_t> : std::true_type {};
#endif

template <typename T> struct is_signed : std::is_signed<T> {};

#ifdef __SIZEOF_INT128__
template <> struct is_signed<__int128_t> : std::true_type {};
template <> struct is_signed<__uint128_t> : std::false_type {};
#endif

template <typename T> T safe_mod(T x, T m) {
    assert(m > 0);
    x %= m;
    if constexpr (is_signed<T>::value) {
        if (x < 0) {
            x += m;
        }
    }
    return x;
}

template <typename T> T gcd(T a, T b) {
    assert(a >= 0);
    assert(b >= 0);
    while (b != 0) {
        const T c = a % b;
        a = b;
        b = c;
    }
    return a;
}

template <typename T> T add_mod(T a, T b, T m) {
    assert(0 <= a && a < m);
    assert(0 <= b && b < m);
    if (a >= m - b) {
        return a - (m - b);
    }
    return a + b;
}

template <typename T> T mul_mod(T a, T b, T m) {
    assert(m > 0);
    a = safe_mod(a, m);
    b = safe_mod(b, m);
#ifdef __SIZEOF_INT128__
    if constexpr (sizeof(T) <= 8) {
        return static_cast<T>(
            (static_cast<__uint128_t>(a) * static_cast<__uint128_t>(b)) %
            static_cast<__uint128_t>(m));
    } else {
#endif
        T res = 0;
        while (b != 0) {
            if ((b & 1) != 0) {
                res = add_mod(res, a, m);
            }
            b >>= 1;
            if (b != 0) {
                a = add_mod(a, a, m);
            }
        }
        return res;
#ifdef __SIZEOF_INT128__
    }
#endif
}

template <typename T> T inv_mod(T a, T m) {
    assert(m > 1);
    a = safe_mod(a, m);
    assert(gcd(a, m) == 1);
    T b = m;
    T x = 1;
    T y = 0;
    while (b != 0) {
        const T q = a / b;
        const T c = a - q * b;
        a = b;
        b = c;
        const T z = safe_mod(x - mul_mod(q, y, m), m);
        x = y;
        y = z;
    }
    assert(a == 1);
    return x;
}

template <typename T> std::pair<T, T> merge_congruence(T r0, T m0, T r1, T m1) {
    assert(0 <= r0 && r0 < m0);
    assert(0 <= r1 && r1 < m1);
    const T g = gcd(m0, m1);
    const T diff = r1 - r0;
    if (diff % g != 0) {
        return {0, 0};
    }
    const T u1 = m1 / g;
    if (u1 == 1) {
        return {r0, m0};
    }
    const T t = mul_mod(diff / g, inv_mod(m0 / g, u1), u1);
    r0 += t * m0;
    m0 *= u1;
    return {r0, m0};
}

template <typename T> std::pair<T, T> solve_linear_congruence(T a, T b, T m) {
    assert(m > 0);
    a = safe_mod(a, m);
    b = safe_mod(b, m);
    const T g = gcd(a, m);
    if (b % g != 0) {
        return {0, 0};
    }
    const T mod = m / g;
    if (mod == 1) {
        return {0, 1};
    }
    const T rem = mul_mod(b / g, inv_mod(a / g, mod), mod);
    return {rem, mod};
}
} // namespace generalized_garner_internal

template <typename R1 = long long, typename R2 = R1, typename T1, typename T2,
          typename M>
std::pair<R1, R2> generalized_garner(const std::vector<T1> &a,
                                     const std::vector<T2> &b,
                                     const std::vector<M> &m) {
    static_assert(generalized_garner_internal::is_integral<R1>::value);
    static_assert(generalized_garner_internal::is_integral<R2>::value);
    static_assert(generalized_garner_internal::is_signed<R1>::value);
    static_assert(generalized_garner_internal::is_signed<R2>::value);
    static_assert(generalized_garner_internal::is_integral<T1>::value);
    static_assert(generalized_garner_internal::is_integral<T2>::value);
    static_assert(generalized_garner_internal::is_integral<M>::value);
    using R = std::common_type_t<R1, R2>;
    static_assert(generalized_garner_internal::is_integral<R>::value);
    static_assert(generalized_garner_internal::is_signed<R>::value);
    assert(a.size() == b.size());
    assert(a.size() == m.size());
    R r0 = 0;
    R m0 = 1;
    const int n = static_cast<int>(a.size());
    for (int i = 0; i < n; ++i) {
        const R mi = static_cast<R>(m[i]);
        assert(mi > 0);
        const auto [r1, m1] =
            generalized_garner_internal::solve_linear_congruence(
                static_cast<R>(a[i]), static_cast<R>(b[i]), mi);
        if (m1 == 0) {
            return {0, 0};
        }
        const auto [nr, nm] =
            generalized_garner_internal::merge_congruence(r0, m0, r1, m1);
        if (nm == 0) {
            return {0, 0};
        }
        r0 = nr;
        m0 = nm;
    }
    return {static_cast<R1>(r0), static_cast<R2>(m0)};
}


#line 7 "verify/yukicoder-2117.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    long long b0, c0, b1, c1;
    std::cin >> b0 >> c0;
    std::cin >> b1 >> c1;
    const std::vector<long long> a = {1, 1};
    const std::vector<long long> b = {c0, c1};
    const std::vector<long long> m = {b0, b1};
    const auto [r, mod] = generalized_garner<long long>(a, b, m);
    if (mod == 0) {
        std::cout << "NaN\n";
    } else {
        std::cout << r << '\n';
    }
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	Chiisai_00	AC	2 ms	3 MB
g++	Chiisai_01	AC	2 ms	3 MB
g++	Chiisai_02	AC	2 ms	4 MB
g++	Chiisai_03	AC	2 ms	3 MB
g++	Chiisai_04	AC	2 ms	3 MB
g++	Chiisai_05	AC	2 ms	3 MB
g++	Chiisai_06	AC	2 ms	3 MB
g++	Chiisai_07	AC	2 ms	3 MB
g++	Chiisai_08	AC	2 ms	3 MB
g++	Chiisai_09	AC	2 ms	4 MB
g++	Ookii_00	AC	2 ms	4 MB
g++	Ookii_01	AC	2 ms	3 MB
g++	Ookii_02	AC	2 ms	4 MB
g++	Ookii_03	AC	2 ms	3 MB
g++	Ookii_04	AC	2 ms	4 MB
g++	Ookii_05	AC	2 ms	4 MB
g++	Ookii_06	AC	2 ms	3 MB
g++	Ookii_07	AC	2 ms	3 MB
g++	Ookii_08	AC	2 ms	4 MB
g++	Ookii_09	AC	2 ms	3 MB
clang++	Chiisai_00	AC	2 ms	4 MB
clang++	Chiisai_01	AC	2 ms	4 MB
clang++	Chiisai_02	AC	2 ms	4 MB
clang++	Chiisai_03	AC	2 ms	4 MB
clang++	Chiisai_04	AC	2 ms	3 MB
clang++	Chiisai_05	AC	2 ms	3 MB
clang++	Chiisai_06	AC	2 ms	3 MB
clang++	Chiisai_07	AC	2 ms	3 MB
clang++	Chiisai_08	AC	2 ms	4 MB
clang++	Chiisai_09	AC	2 ms	3 MB
clang++	Ookii_00	AC	2 ms	3 MB
clang++	Ookii_01	AC	2 ms	3 MB
clang++	Ookii_02	AC	2 ms	4 MB
clang++	Ookii_03	AC	2 ms	4 MB
clang++	Ookii_04	AC	2 ms	3 MB
clang++	Ookii_05	AC	2 ms	4 MB
clang++	Ookii_06	AC	2 ms	4 MB
clang++	Ookii_07	AC	2 ms	4 MB
clang++	Ookii_08	AC	2 ms	3 MB
clang++	Ookii_09	AC	2 ms	3 MB

Back to top page