Loading [Contrib]/a11y/accessibility-menu.js
$\newcommand{\O}{\mathrm{O}}$ My Algorithm : kopricky アルゴリズムライブラリ

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

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$ は法の値)

コード

  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 提出コード