verify/standalone-generalized-garner.test.cpp

• View this file on GitHub
• Last update: 2026-06-05 17:58:28+09:00

Depends on

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

Code

// competitive-verifier: STANDALONE

#include <cassert>
#include <vector>

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

namespace {
struct Equation {
    long long a;
    long long b;
    long long m;
};

long long safe_mod_ll(long long x, long long m) {
    assert(m > 0);
    x %= m;
    if (x < 0) {
        x += m;
    }
    return x;
}

long long gcd_ll(long long a, long long b) {
    if (a < 0) {
        a = -a;
    }
    if (b < 0) {
        b = -b;
    }
    while (b != 0) {
        const long long c = a % b;
        a = b;
        b = c;
    }
    return a;
}

long long lcm_ll(long long a, long long b) { return a / gcd_ll(a, b) * b; }

bool satisfy(long long x, const Equation &e) {
    return safe_mod_ll(e.a * x - e.b, e.m) == 0;
}

void check(const std::vector<Equation> &eqs) {
    std::vector<long long> a;
    std::vector<long long> b;
    std::vector<long long> m;
    long long period = 1;
    for (const Equation &e : eqs) {
        a.push_back(e.a);
        b.push_back(e.b);
        m.push_back(e.m);
        period = lcm_ll(period, e.m);
    }
    const auto got = generalized_garner<long long>(a, b, m);
    std::vector<bool> good(period, false);
    bool exists = false;
    for (long long x = 0; x < period; ++x) {
        bool ok = true;
        for (const Equation &e : eqs) {
            if (!satisfy(x, e)) {
                ok = false;
            }
        }
        good[x] = ok;
        if (ok) {
            exists = true;
        }
    }
    if (!exists) {
        assert(got.first == 0);
        assert(got.second == 0);
        return;
    }
    long long want_rem = 0;
    while (!good[want_rem]) {
        ++want_rem;
    }
    long long want_mod = period;
    for (long long x = want_rem + 1; x < period; ++x) {
        if (good[x]) {
            want_mod = gcd_ll(want_mod, x - want_rem);
        }
    }
    assert(got.first == want_rem);
    assert(got.second == want_mod);
}

void self_test_small() {
    check({});
    std::vector<Equation> eqs;
    for (long long m = 1; m <= 6; ++m) {
        for (long long a = -5; a <= 5; ++a) {
            for (long long b = -5; b <= 5; ++b) {
                eqs.push_back({a, b, m});
            }
        }
    }
    for (const Equation &e0 : eqs) {
        check({e0});
    }
    for (const Equation &e0 : eqs) {
        for (const Equation &e1 : eqs) {
            check({e0, e1});
        }
    }
    for (int i = 0; i < static_cast<int>(eqs.size()); i += 37) {
        for (int j = 0; j < static_cast<int>(eqs.size()); j += 41) {
            for (int k = 0; k < static_cast<int>(eqs.size()); k += 43) {
                check({eqs[i], eqs[j], eqs[k]});
            }
        }
    }
}

#ifdef __SIZEOF_INT128__
void self_test_int128() {
    using i128 = __int128_t;
    const i128 x0 = 123456789;
    const i128 m0 = i128(1) << 70;
    const i128 m1 = i128(1) << 69;
    {
        const std::vector<i128> a = {3, 5};
        const std::vector<i128> b = {3 * x0, 5 * x0};
        const std::vector<i128> m = {m0, m1};
        const auto res = generalized_garner<i128>(a, b, m);
        assert(res.first == x0);
        assert(res.second == m0);
    }
    {
        const std::vector<i128> a = {1, 1};
        const std::vector<i128> b = {0, 1};
        const std::vector<i128> m = {m0, m1};
        const auto res = generalized_garner<i128>(a, b, m);
        assert(res.first == 0);
        assert(res.second == 0);
    }
}
#endif
} // namespace

int main() {
    self_test_small();
#ifdef __SIZEOF_INT128__
    self_test_int128();
#endif
    return 0;
}

#line 1 "verify/standalone-generalized-garner.test.cpp"
// competitive-verifier: STANDALONE

#include <cassert>
#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 では剰余乗算をダブリングで行う。

#line 12 "math/number-theory/generalized-garner.hpp"
#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/standalone-generalized-garner.test.cpp"

namespace {
struct Equation {
    long long a;
    long long b;
    long long m;
};

long long safe_mod_ll(long long x, long long m) {
    assert(m > 0);
    x %= m;
    if (x < 0) {
        x += m;
    }
    return x;
}

long long gcd_ll(long long a, long long b) {
    if (a < 0) {
        a = -a;
    }
    if (b < 0) {
        b = -b;
    }
    while (b != 0) {
        const long long c = a % b;
        a = b;
        b = c;
    }
    return a;
}

long long lcm_ll(long long a, long long b) { return a / gcd_ll(a, b) * b; }

bool satisfy(long long x, const Equation &e) {
    return safe_mod_ll(e.a * x - e.b, e.m) == 0;
}

void check(const std::vector<Equation> &eqs) {
    std::vector<long long> a;
    std::vector<long long> b;
    std::vector<long long> m;
    long long period = 1;
    for (const Equation &e : eqs) {
        a.push_back(e.a);
        b.push_back(e.b);
        m.push_back(e.m);
        period = lcm_ll(period, e.m);
    }
    const auto got = generalized_garner<long long>(a, b, m);
    std::vector<bool> good(period, false);
    bool exists = false;
    for (long long x = 0; x < period; ++x) {
        bool ok = true;
        for (const Equation &e : eqs) {
            if (!satisfy(x, e)) {
                ok = false;
            }
        }
        good[x] = ok;
        if (ok) {
            exists = true;
        }
    }
    if (!exists) {
        assert(got.first == 0);
        assert(got.second == 0);
        return;
    }
    long long want_rem = 0;
    while (!good[want_rem]) {
        ++want_rem;
    }
    long long want_mod = period;
    for (long long x = want_rem + 1; x < period; ++x) {
        if (good[x]) {
            want_mod = gcd_ll(want_mod, x - want_rem);
        }
    }
    assert(got.first == want_rem);
    assert(got.second == want_mod);
}

void self_test_small() {
    check({});
    std::vector<Equation> eqs;
    for (long long m = 1; m <= 6; ++m) {
        for (long long a = -5; a <= 5; ++a) {
            for (long long b = -5; b <= 5; ++b) {
                eqs.push_back({a, b, m});
            }
        }
    }
    for (const Equation &e0 : eqs) {
        check({e0});
    }
    for (const Equation &e0 : eqs) {
        for (const Equation &e1 : eqs) {
            check({e0, e1});
        }
    }
    for (int i = 0; i < static_cast<int>(eqs.size()); i += 37) {
        for (int j = 0; j < static_cast<int>(eqs.size()); j += 41) {
            for (int k = 0; k < static_cast<int>(eqs.size()); k += 43) {
                check({eqs[i], eqs[j], eqs[k]});
            }
        }
    }
}

#ifdef __SIZEOF_INT128__
void self_test_int128() {
    using i128 = __int128_t;
    const i128 x0 = 123456789;
    const i128 m0 = i128(1) << 70;
    const i128 m1 = i128(1) << 69;
    {
        const std::vector<i128> a = {3, 5};
        const std::vector<i128> b = {3 * x0, 5 * x0};
        const std::vector<i128> m = {m0, m1};
        const auto res = generalized_garner<i128>(a, b, m);
        assert(res.first == x0);
        assert(res.second == m0);
    }
    {
        const std::vector<i128> a = {1, 1};
        const std::vector<i128> b = {0, 1};
        const std::vector<i128> m = {m0, m1};
        const auto res = generalized_garner<i128>(a, b, m);
        assert(res.first == 0);
        assert(res.second == 0);
    }
}
#endif
} // namespace

int main() {
    self_test_small();
#ifdef __SIZEOF_INT128__
    self_test_int128();
#endif
    return 0;
}

Back to top page