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);
- // }