中国剰余定理
概要
素数 MOD が幾つか与えられたとき、その総積 MOD が分かる。
問題
コード
code:garner.cpp
class GarnerAlgorithm {
private:
inline i64 mod(i64 x, i64 mod) {
x %= mod;
return (x < 0 ? x + mod : x);
}
i64 extGCD(i64 a, i64 b, i64 &p, i64 &q) {
if(!b) {
p = 1;
q = 0;
return a;
}
i64 d = extGCD(b, a % b, q, p);
q -= a / b * p;
return d;
}
i64 modinv(i64 a, i64 m) {
i64 x = 0, y = 0;
extGCD(a, m, x, y);
return mod(x, m);
}
public:
// coprime
i64 Garner(std::vector<i64> b, std::vector<i64> m, i64 MOD = 1e18) {
m.push_back(MOD);
std::vector<i64> coeffs(m.size(), 1);
std::vector<i64> constants(m.size(), 0);
for(int k = 0; k < b.size(); ++k) {
i64 t = mod((bk - constantsk) * modinv(coeffsk, mk), mk); for(int i = k + 1; i < m.size(); ++i) {
(constantsi += t * coeffsi) %= mi; }
}
return constants.back();
}
};