Chinese Remainder Theorem
コードについての説明
Chinese Remainder Theorem(中国剰余定理) は $p_1$ と $p_2$ が互いに素で $x = q_1\ (\mathrm{mod}\ p_1), x = q_2\ (\mathrm{mod}\ p_2)$ が成り立つとき, これを満たす $x$ は $[0, p_1 p_2)$ にただ一つ存在するという定理のことであり, 以下の実装は実際にその唯一の解を求めるアルゴリズムである
結局式変形すると拡張ユークリッドの互除法(extgcd)を解くことと同じであることが分かり, それを実装する. 以下の実装では一般の場合(法が互いに素でない場合)に拡張したものも含まれている.
時間計算量: $\O (\log p)$ ($p$ は法の値)
コード
template<typename T>
T gcd(T a,T b)
{
if(a % b == 0){
return b;
}else{
return gcd(b,a%b);
}
}
template <typename T>
void extgcd(T a, T b, T& x, T& y)
{
if(b != 0){
extgcd(b,a%b,y,x);
y -= (a/b)*x;
}else{
x = 1;
y = 0;
}
}
// (value, mod)
// 型 T は積が収まるようにとる(引数が int なら long long にする)
template <typename T>
pair<T, T> CRT(const pair<T, T>& a1, const pair<T, T>& a2)
{
const T v1 = a1.first, m1 = a1.second;
const T v2 = a2.first, m2 = a2.second;
if(v1 == v2) return make_pair(v1,m1*m2);
T x, y;
extgcd(m1, m2, x, y);
x *= (v2 - v1), y *= (v2 - v1);
const T m = m1 * m2;
const T res = ((m1 * (x % m2)) + v1) % m;
return make_pair((res >= 0 ? res : res + m), m);
}
//modどうしが互いに素でないとき
//(value, mod)
// template <typename T>
// pair<T, T> CRT(const pair<T, T>& a1, const pair<T, T>& a2)
// {
// const T v1 = a1.first, m1 = a1.second;
// const T v2 = a2.first, m2 = a2.second;
// T g = gcd(m1, m2);
// T dev = (v2 - v1) / g;
// T mod = abs(v2 - v1) % g;
// if(mod) return make_pair(-1,-1);
// T x, y;
// extgcd(m1 / g, m2 / g, x, y);
// x *= dev, y *= dev;
// const T m = m1 / g * m2;
// const T res = ((m1 * (x % (m2 / g))) + v1) % m;
// return make_pair((res >= 0 ? res : res + m), m);
// }