中国剰余定理

概要

$x = a_1 \pmod{m_1}$ かつ $x = a_2 \pmod{m_2}$ を満たす最小の非負整数 $x$ を求めます．存在しないなら $-1$ を返します．そのような $x$ は $a_1 = a_2 \pmod{\gcd(m_1, m_2)}$ なら $\mathrm{mod} \ \mathrm{lcm}(m_1,m_2)$ で一意に定まり，そうでないなら存在しません．この事実を中国剰余定理といいます(名前にはバリエーションがあります)．式の数が増えても繰り返し使えばいいです．代数を勉強するともっとよく分かりそう．

計算量

$O(\log(\min(m_1 , m_2)))$

使い方

すごく簡単にオーバーフローするので注意．

crt(a1,m1,a2,m2): x % m1 = a1, x % m2 = a2, 0 < x < lcm(m1, m2) を満たす x を求める
crt(a,m): 繰り返して全ての条件を満たす x を求める

実装

using lll = __int128_t;
std::pair<lll, lll> crt(lll a1, lll m1, lll a2, lll m2) {
    auto normal = [](lll x, lll m) { return x >= -x ? x % m : m - (-x) % m; };
    auto modmul = [&normal](lll a, lll b, lll m) { return normal(a, m) * normal(b, m) % m; };
    auto extgcd = [](lll a, lll b, lll &x, lll &y) {
        for (lll u = y = 1, v = x = 0; a;) {
            lll q = b / a;
            std::swap(x -= q * u, u);
            std::swap(y -= q * v, v);
            std::swap(b -= q * a, a);
        }
        return b;
    };
    lll k1, k2;
    lll g = extgcd(m1, m2, k1, k2);
    if (normal(a1, g) != normal(a2, g))
        return std::make_pair(-1, -1);
    else {
        lll l = m1 / g * m2;
        lll x = a1 + modmul(modmul((a2 - a1) / g, k1, l), m1, l);
        return std::make_pair(x, l);
    }
}
std::pair<lll, lll> crt(std::vector<lll> a, std::vector<lll> m) {
    lll mod = 1, ans = 0;
    int n = a.size();
    for (int i = 0; i < n; i++) {
        std::tie(ans, mod) = crt(ans, mod, a[i], m[i]);
        if (ans == -1) return std::make_pair(-1, -1);
    }
    return std::make_pair(ans, mod);
}

検証

yukicoder No.186 中華風 (Easy) (Submittion)

中国剰余定理

概要

計算量

使い方

実装

検証

参考文献