chinese_remainder_theorem
(src/math/chinese_remainder_theorem.hpp)

• View this file on GitHub
• Last update: 2024-11-09 02:03:28+09:00
• Include: #include "src/math/chinese_remainder_theorem.hpp"

chinese_remainder_theorem

pair<ll, ll> chinese_remainder_theorem(vectpr<ll> r, vector<ll> m)

同じ長さの配列 $r, m$ を渡します．
この配列の長さを $n$ としたとき，

\[x \equiv r[i] \pmod{m[i]}, \forall i \in \lbrace 0,1,\cdots, n - 1 \rbrace\]

を解きます．
答えは (存在するならば) $y, z (0 \leq y < z = \mathrm{lcm}(m[i]))$ を用いて $x \equiv y \pmod z$ の形で書けることが知られており，この $(y, z)$ をpairとして返します．
答えがない場合は $(0, 0)$ を返します．
$n = 0$ の時は $(0, 1)$ を返します．

制約

• $r.\mathrm{size}() = m.\mathrm{size}()$
• $1 \le m[i]$
• $\mathrm{lcm} (m[i])$ が ll に収まる．

計算量

• $O(n \log \mathrm{lcm} (m[i]))$

Depends on

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

Verified with

• verify/yukicoder/186.test.cpp

Code

#pragma once
#include "../template/template.hpp"
#include "./inv_gcd.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 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};
}

Back to top page