sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "math/number-theory/garner.hpp"
Garner のアルゴリズムは,連立合同式 $x \equiv b_i \mod m_i \quad (i=1,\dots,n)$ の解を求めるアルゴリズムである.
$m_i$が pairwise coprime であるとき,この連立合同式には法$m = m_1\dots m_n$のもとでただ一つの解が存在することが中国の剰余定理によって保証される.
long long garner(vector<long long> b, vector<long long> m, long long mod)
#pragma once #include <vector> #include "extgcd.hpp" long long garner(const std::vector<long long>& b, std::vector<long long> m, long long mod) { m.push_back(mod); const int n = m.size(); std::vector<long long> coeffs(n, 1); std::vector<long long> consts(n, 0); for (int k = 0; k < n - 1; ++k) { long long t = (b[k] - consts[k]) * mod_inv(coeffs[k], m[k]) % m[k]; if (t < 0) t += m[k]; for (int i = k + 1; i < n; ++i) { consts[i] = (consts[i] + t * coeffs[i]) % m[i]; coeffs[i] = coeffs[i] * m[k] % m[i]; } } return consts.back(); }
#line 2 "math/number-theory/garner.hpp" #include <vector> #line 2 "math/number-theory/extgcd.hpp" #include <algorithm> #include <utility> std::pair<long long, long long> extgcd(long long a, long long b) { long long s = a, sx = 1, sy = 0, t = b, tx = 0, ty = 1; while (t) { long long q = s / t; std::swap(s -= t * q, t); std::swap(sx -= tx * q, tx); std::swap(sy -= ty * q, ty); } return {sx, sy}; } long long mod_inv(long long a, long long mod) { long long inv = extgcd(a, mod).first; return (inv % mod + mod) % mod; } #line 5 "math/number-theory/garner.hpp" long long garner(const std::vector<long long>& b, std::vector<long long> m, long long mod) { m.push_back(mod); const int n = m.size(); std::vector<long long> coeffs(n, 1); std::vector<long long> consts(n, 0); for (int k = 0; k < n - 1; ++k) { long long t = (b[k] - consts[k]) * mod_inv(coeffs[k], m[k]) % m[k]; if (t < 0) t += m[k]; for (int i = k + 1; i < n; ++i) { consts[i] = (consts[i] + t * coeffs[i]) % m[i]; coeffs[i] = coeffs[i] * m[k] % m[i]; } } return consts.back(); }