Garner's Algorithm

garner.hpp

using LL = long long;
auto garner(const std::vector<LL> &A, const std::vector<LL> &M, LL mod) {
    assert(A.size() == M.size());
    auto X = A;
    for (size_t i = 0; i < A.size(); ++i) {
        for (size_t j = 0; j < i; ++j) {
            X[i] = mod_inv(M[j], M[i]) * (X[i] - X[j]) % M[i];
            if (X[i] < 0) X[i] += M[i];
        }
    }
    LL coeff = 1, ans = 0;
    for (size_t i = 0; i < A.size(); ++i) {
        ans = (ans + coeff * X[i]) % mod;
        coeff = coeff * M[i] % mod;
    }
    return ans;
}

garner2.hpp

using LL = long long;
auto garner2(const std::vector<LL> &A, std::vector<LL> M, LL mod) {
  assert(A.size() == M.size());  
  M.emplace_back(mod);
    std::vector<LL> X(A.size());
    std::vector<LL> coeffs(M.size(), 1);
    std::vector<LL> consts(M.size(), 0);
    for (size_t k = 0; k < A.size(); ++k) {
        X[k] = (A[k] - consts[k]) * mod_inv(coeffs[k], M[k]) % M[k];
        if (X[k] < 0) X[k] += M[k];
        for (size_t i = k + 1; i < M.size(); ++i) {
            consts[i] = (consts[i] + X[k] * coeffs[i]) % M[i];
            coeffs[i] = coeffs[i] * M[k] % M[i];
        }
    }
    return consts.back();
}