:warning: Garner のアルゴリズム
(math/garner.hpp)

$x\bmod m_1=r_1,x\bmod m_2=r_2,\dots,x\bmod m_n=r_n$ を満たす最小の非負整数 $x$ を求める．ただし $m_1,m_2,\dots,m_n$ のどの 2 つも互いに素．

解の mod をとらないとき

まず $n=2$ のときを考える．

$x=r_1+m_1y$ とおくと $y\equiv(r_2-r_1)m_1^{-1}\pmod{m_2}$ である．

従って $x=r_1+m_1((r_2-r_1)m_1^{-1}\bmod{m_2})$ として $x$ が求められる．

複数 mod のときも繰り返し用いればよい．

解の mod をとるとき

まず$n=2$ のときを考える．

$m_0$ を任意の mod とする（$m_1$ および $m_2$ と互いに素でなくとも構わない）．

$(x\bmod m_1)\bmod m_i$ の値がわかっているときに $(x\bmod m_1m_2)\bmod m_i$ の値を求める．

そのためには $(r_2-r_1)m_1^{-1}\bmod{m_2}$ の値がわかればよく，これは $(x\bmod m_1)\bmod m_2,m_1\bmod m_2$ の値から求められる．

その値（$y$ とする）が求まれば，計算済みの値にそれぞれ $m_1y$ を適宜 mod をとって加えればよい．

一般の $n$ に対しては，以下のように定める．

\[\begin{align*} x_i&=\left(\sum_{j=1}^{i-1}y_j\left(\prod_{l=1}^{j-1}m_l\right)\right)\bmod{m_i}\quad (1\leq i\leq n)\\ y_i&=(r_i-x_i)\left(\prod_{l=1}^{i-1}m_l\right)^{-1}\bmod{m_i}\quad(1\leq i\leq n). \end{align*}\]

このとき実際の値は $y_1+m_1y_2+\cdots+m_1\cdots m_{i-1}y_i$ であるから，これを適宜 mod を取り計算すればよい．

$x$ の値が非常に大きいような場合であっても，四則演算が各 mod の範囲でさえ行えれば計算できる．

オンライン化

解の mod をとらないとき，単に直近の mod と解を持てばよい．

解の mod をとるとき，$m_i,y_i$ の値を管理しておけばよい．

Depends on

Code

#pragma once
#include "math/util.hpp"

template <class T>
T Garner(const vector<T>& r, const vector<T>& m) {
  int n = r.size();
  if (n == 0) return 0;
  T p = 1, x = 0;
  for (int i = 0; i < n; i++) {
    T t = (r[i] - x % m[i] + m[i]) * Math::inv_mod(p, m[i]) % m[i];
    x += t * p;
    p *= m[i];
  }
  return x;
}
template <class T>
T Garner(const vector<T>& r, const vector<T>& m, T mod) {
  int n = r.size();
  if (n == 0) return 0;
  vector<T> y(n);
  for (int i = 0; i < n; i++) {
    T x = 0, p = 1;
    for (int j = 0; j < i; j++) {
      x = (x + y[j] * p) % m[i];
      p = p * m[j] % m[i];
    }
    y[i] = (r[i] - x + m[i]) * Math::inv_mod(p, m[i]) % m[i];
  }
  T res = 0;
  for (int i = n - 1; i >= 0; i--) res = (res * m[i] + y[i]) % mod;
  return res;
}

/**
 * @brief Garner のアルゴリズム
 * @docs docs/math/garner.md
 */
#line 2 "math/util.hpp"

namespace Math {
template <class T>
T safe_mod(T a, T b) {
  assert(b != 0);
  if (b < 0) a = -a, b = -b;
  a %= b;
  return a >= 0 ? a : a + b;
}
template <class T>
T floor(T a, T b) {
  assert(b != 0);
  if (b < 0) a = -a, b = -b;
  return a >= 0 ? a / b : (a + 1) / b - 1;
}
template <class T>
T ceil(T a, T b) {
  assert(b != 0);
  if (b < 0) a = -a, b = -b;
  return a > 0 ? (a - 1) / b + 1 : a / b;
}
long long isqrt(long long n) {
  if (n <= 0) return 0;
  long long x = sqrt(n);
  while ((x + 1) * (x + 1) <= n) x++;
  while (x * x > n) x--;
  return x;
}
// return g=gcd(a,b)
// a*x+b*y=g
// - b!=0 -> 0<=x<|b|/g
// - b=0  -> ax=g
template <class T>
T ext_gcd(T a, T b, T& x, T& y) {
  T a0 = a, b0 = b;
  bool sgn_a = a < 0, sgn_b = b < 0;
  if (sgn_a) a = -a;
  if (sgn_b) b = -b;
  if (b == 0) {
    x = sgn_a ? -1 : 1;
    y = 0;
    return a;
  }
  T x00 = 1, x01 = 0, x10 = 0, x11 = 1;
  while (b != 0) {
    T q = a / b, r = a - b * q;
    x00 -= q * x01;
    x10 -= q * x11;
    swap(x00, x01);
    swap(x10, x11);
    a = b, b = r;
  }
  x = x00, y = x10;
  if (sgn_a) x = -x;
  if (sgn_b) y = -y;
  if (b0 != 0) {
    a0 /= a, b0 /= a;
    if (b0 < 0) a0 = -a0, b0 = -b0;
    T q = x >= 0 ? x / b0 : (x + 1) / b0 - 1;
    x -= b0 * q;
    y += a0 * q;
  }
  return a;
}
template <class T>
T inv_mod(T x, T m) {
  x %= m;
  if (x < 0) x += m;
  T a = m, b = x;
  T y0 = 0, y1 = 1;
  while (b > 0) {
    T q = a / b;
    swap(a -= q * b, b);
    swap(y0 -= q * y1, y1);
  }
  if (y0 < 0) y0 += m / a;
  return y0;
}
template <class T>
T pow_mod(T x, T n, T m) {
  x = (x % m + m) % m;
  T y = 1;
  while (n) {
    if (n & 1) y = y * x % m;
    x = x * x % m;
    n >>= 1;
  }
  return y;
}
constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
  if (m == 1) return 0;
  unsigned int _m = (unsigned int)(m);
  unsigned long long r = 1;
  unsigned long long y = x % m;
  if (y >= m) y += m;
  while (n) {
    if (n & 1) r = (r * y) % _m;
    y = (y * y) % _m;
    n >>= 1;
  }
  return r;
}
};  // namespace Math
#line 3 "math/garner.hpp"

template <class T>
T Garner(const vector<T>& r, const vector<T>& m) {
  int n = r.size();
  if (n == 0) return 0;
  T p = 1, x = 0;
  for (int i = 0; i < n; i++) {
    T t = (r[i] - x % m[i] + m[i]) * Math::inv_mod(p, m[i]) % m[i];
    x += t * p;
    p *= m[i];
  }
  return x;
}
template <class T>
T Garner(const vector<T>& r, const vector<T>& m, T mod) {
  int n = r.size();
  if (n == 0) return 0;
  vector<T> y(n);
  for (int i = 0; i < n; i++) {
    T x = 0, p = 1;
    for (int j = 0; j < i; j++) {
      x = (x + y[j] * p) % m[i];
      p = p * m[j] % m[i];
    }
    y[i] = (r[i] - x + m[i]) * Math::inv_mod(p, m[i]) % m[i];
  }
  T res = 0;
  for (int i = n - 1; i >= 0; i--) res = (res * m[i] + y[i]) % mod;
  return res;
}

/**
 * @brief Garner のアルゴリズム
 * @docs docs/math/garner.md
 */
Back to top page