My Algorithm : kopricky アルゴリズムライブラリ

Garner Algorithm

コードについての説明

Garner のアルゴリズムは中国剰余定理の拡張で, ある数 $x(0 \le x < \Pi p_i)$ について $p_i$ で割った余りが $a_i (i = 1, \ldots ,n)$ という情報 $n$ 個与えられたときにその $x$ を $mod$ で割った余りを効率よく求めるアルゴリズムである. ただし $p_i$ は互いに素であるとする.
$x$ がとても大きい数であっても $x \% mod$ を overflow することなく求めることができるのがうれしい.
(参考 1) や (参考 2) を参考に理解した. garner のアルゴリズムについては分かりやすい解説を書いている人が多いので他の人のものを参考にしてもらいたい.

時間計算量: $\O (n^2 + n \log (\max p_i))$

コード

template<typename T>
T mod_add(const T a, const T b, const T mod){
    return (a + b) % mod;
}
 
template<typename T>
T mod_mul(const T a, const T b, const T mod){
    return a * b % mod;
}
 
template<typename T>
T mod_inv(T a, T mod){
    T u[] = {a, 1, 0}, v[] = {mod, 0, 1}, t;
    while(*v){
        t = *u / *v;
        swap(u[0] -= t * v[0], v[0]);
        swap(u[1] -= t * v[1], v[1]);
        swap(u[2] -= t * v[2], v[2]);
    }
    u[1] %= mod;
    return (u[1] < 0) ? (u[1] + mod) : u[1];
}
 
template<typename T>
T garner(const vector<T>& a, vector<T> p, const T mod){
    const unsigned int sz = a.size();
    vector<T> kp(sz + 1, 0), rmult(sz + 1, 1);
    p.push_back(mod);
    for(unsigned int i = 0; i < sz; ++i){
        T x = mod_mul(a[i] - kp[i], mod_inv(rmult[i], p[i]), p[i]);
        x = (x < 0) ? (x + p[i]) : x;
        for(unsigned int j = i + 1; j < sz + 1; ++j){
            kp[j] = mod_add(kp[j], rmult[j] * x, p[j]);
            rmult[j] = mod_mul(rmult[j], p[i], p[j]);
        }
    }
    return kp[sz];
}

verify 用の問題

yukicoder : 中華風 (Hard) 提出コード