Garner's Algorithm

FPSで使う

Spec

\(m_0, \cdots, m_{k-1} \)が互いに素とする.
\( x < \prod{m_i} \)を満たす\( x \)について, \( x \mod m_i \)がわかっている時,
\( O(k^2 + k \log m) \)で \( x \mod M \) を求めることができる.

Code

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

i64 pow_mod(i64 x, i64 r, i64 mod) {
  i64 ans = 1;
  while(r) {
    if(r & 1) ans = (ans * x) % mod;
    r >>= 1;
    x = x * x % mod;
  }
  return ans;
}

i64 inv_mod(i64 x, i64 mod) {
  return pow_mod(x, mod - 2, mod);
}

i64 garner(const vector<i64> &x, vector<i64> mods, i64 mod) {
  mods.emplace_back(mod);
  vector<i64> coeffs(x.size() + 1, 1);
  vector<i64> constants(x.size() + 1, 0);
  for(i64 i = 0; i < x.size(); i++) {
    i64 v = (x[i] - constants[i]) * inv_mod(coeffs[i], mods[i]) % mods[i];
    if(v < 0) v += mods[i];
    for(i64 j = i + 1; j < x.size() + 1; j++) {
      constants[j] = (constants[j] + coeffs[j] * v) % mods[j];
      coeffs[j] = (coeffs[j] * mods[i]) % mods[j];
    }
  }
  return constants.back();
}