Garnerのアルゴリズム

目的

$n$個の合同式 $y = x_i\mod m_i$があります。ここで任意の$i,j(i\neq j)$について$m_i$と$m_j$は互いに素だと仮定しています。 この連立合同式を満たす非負の整数解であって最小である$y$について$y \mod M$を計算します。

計算量

$O(n^2)$

使い方

long garner(long[] x, long[] m, long M)
$x[i]=x_i$、$m[i]=m_i$としたときの$y \mod M$をreturn。

ソースコード

long garner(long[] x, long[] m, long M) {
    int n = x.length;
    long[] gamma = new long[n];
    for (int i = 0; i < n; ++i) {
	long prd = 1;
	for (int j = 0; j < i; ++j) {
	    prd = prd * m[j] % m[i];
	}
	gamma[i] = inv(prd, m[i]);
    }

    long[] v = new long[n];
    v[0] = x[0];
    for (int i = 1; i < n; ++i) {
	long tmp = v[i - 1];
	for (int j = i - 2; j >= 0; --j) {
	    tmp = (tmp * m[j] % m[i] + v[j]) % m[i];
	}
	v[i] = (x[i] - tmp) * gamma[i] % m[i];
	while (v[i] < 0)
	    v[i] += m[i];
    }
    long ret = 0;
    for (int i = v.length - 1; i >= 0; --i) {
	ret = (ret * m[i] % M + v[i]) % M;
    }
    return ret;
}

Verified

yukicoder No.569