Garner's Algorithm
(math/number-theory/garner.hpp)

• View this file on GitHub
• Last update: 2024-01-08 17:31:43+09:00
• Include: #include "math/number-theory/garner.hpp"

Description

Garner のアルゴリズムは，連立合同式 $x \equiv b_i \mod m_i \quad (i=1,\dots,n)$ の解を求めるアルゴリズムである．

$m_i$が pairwise coprime であるとき，この連立合同式には法$m = m_1\dots m_n$のもとでただ一つの解が存在することが中国の剰余定理によって保証される．

Operations

• long long garner(vector<long long> b, vector<long long> m, long long mod)
  • 連立合同式を満たす最小の非負整数を法$mod$で求める．
  • 時間計算量: $O(n^2)$

Reference

• 中国剰余定理 (CRT) の解説と、それを用いる問題のまとめ
• Chinese Remainder Theorem

Depends on

• Extended Euclidean Algorithm (math/number-theory/extgcd.hpp)

Required by

• Arbitrary Mod Convolution (convolution/arbitrary_mod_convolution.hpp)

Verified with

• test/yosupo/convolution_mod_1000000007.test.cpp

Code

#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();
}

Back to top page