Processing math: 100%
My Algorithm : kopricky アルゴリズムライブラリ

kopricky アルゴリズムライブラリ

Chinese Remainder Theorem

コードについての説明

Chinese Remainder Theorem(中国剰余定理) は p1 と p2 が互いに素で x=q1 (mod p1),x=q2 (mod p2) が成り立つとき, これを満たす x は [0,p1p2) にただ一つ存在するという定理のことであり, 以下の実装は実際にその唯一の解を求めるアルゴリズムである
結局式変形すると拡張ユークリッドの互除法(extgcd)を解くことと同じであることが分かり, それを実装する. 以下の実装では一般の場合(法が互いに素でない場合)に拡張したものも含まれている.

時間計算量: O(logp) (p は法の値)

コード

  1. template<typename T>
  2. T gcd(T a,T b)
  3. {
  4.     if(a % b == 0){
  5.         return b;
  6.     }else{
  7.         return gcd(b,a%b);
  8.     }
  9. }
  10.  
  11. template <typename T>
  12. void extgcd(T a, T b, T& x, T& y)
  13. {
  14.     if(b != 0){
  15.         extgcd(b,a%b,y,x);
  16.         y -= (a/b)*x;
  17.     }else{
  18.         x = 1;
  19.         y = 0;
  20.     }
  21. }
  22.  
  23. // (value, mod)
  24. // 型 T は積が収まるようにとる(引数が int なら long long にする)
  25. template <typename T>
  26. pair<T, T> CRT(const pair<T, T>& a1, const pair<T, T>& a2)
  27. {
  28.     const T v1 = a1.first, m1 = a1.second;
  29.     const T v2 = a2.first, m2 = a2.second;
  30.     if(v1 == v2) return make_pair(v1,m1*m2);
  31.     T x, y;
  32.     extgcd(m1, m2, x, y);
  33.     x *= (v2 - v1), y *= (v2 - v1);
  34.     const T m = m1 * m2;
  35.     const T res = ((m1 * (x % m2)) + v1) % m;
  36.     return make_pair((res >= 0 ? res : res + m), m);
  37. }
  38.  
  39. //modどうしが互いに素でないとき
  40. //(value, mod)
  41. // template <typename T>
  42. // pair<T, T> CRT(const pair<T, T>& a1, const pair<T, T>& a2)
  43. // {
  44. //     const T v1 = a1.first, m1 = a1.second;
  45. //     const T v2 = a2.first, m2 = a2.second;
  46. //     T g = gcd(m1, m2);
  47. //     T dev = (v2 - v1) / g;
  48. //     T mod = abs(v2 - v1) % g;
  49. //     if(mod) return make_pair(-1,-1);
  50. //     T x, y;
  51. //     extgcd(m1 / g, m2 / g, x, y);
  52. //     x *= dev, y *= dev;
  53. //     const T m = m1 / g * m2;
  54. //     const T res = ((m1 * (x % (m2 / g))) + v1) % m;
  55. //     return make_pair((res >= 0 ? res : res + m), m);
  56. // }

verify 用の問題

Codeforces : Billiard 提出コード