Chinese Remainder Theorem (中国剰余定理)
(lib/math/crt.hpp)

• View this file on GitHub
• Last update: 2025-02-15 00:03:46+09:00
• Include: #include "lib/math/crt.hpp"

Chinese Remainder Theorem (中国剰余定理)

使い方

• CRT::extGCD(a, b, x, y): $ax + by =$ gcd($a, b$) となる $x, y$ を求めます。
• CRT::ChineseRem(b, m): 中国剰余定理の計算を行います。返り値を (r, m) とすると解は x ≡ r (mod. m)、解なしの場合は (0, -1) を返します。

注意: lcmのオーバーフローに注意する。

計算量

• CRT::extGCD(a, b, x, y): $\mathrm{O}(\log a)$
• CRT::ChineseRem(b, m): $\mathrm{O}(N \log \mathrm{lcm}(m))$ (配列の長さを $N$ とする)

Required by

• Number Theoretic Transform (lib/convolution/ntt.hpp)
• Partition Function (分割数) (lib/enumerative_combinatorics/partition_function.hpp)
• Stirling Number of the Second Kind (第 2 種スターリング数) (lib/enumerative_combinatorics/stirling_number_2nd.hpp)
• Subset Sum (lib/enumerative_combinatorics/subset_sum.hpp)
• Bell Number (ベル数) (lib/math/bell_number.hpp)
• Bernoulli Number (ベルヌーイ数) (lib/math/bernoulli_number.hpp)
• Bostan-Mori (lib/polynomial/bostan_mori.hpp)
• Formal Power Series (形式的冪級数) (lib/polynomial/formal_power_series.hpp)
• Multipoint Evaluation (多点評価) (lib/polynomial/multipoint_evaluation.hpp)
• Polynomial Interpolation (多項式補間) (lib/polynomial/polynomial_interpolation.hpp)
• Product of Polynomial Sequence (多項式列の総積) (lib/polynomial/product_of_polynomial_sequence.hpp)
• Taylor Shift (lib/polynomial/taylor_shift.hpp)
• Wildcard Pattern Matching (lib/string/wildcard_pattern_matching.hpp)

Verified with

• test/library_checker/convolution/convolution.test.cpp
• test/library_checker/convolution/convolution_mod_1000000007.test.cpp
• test/library_checker/enumerative_combinatorics/partition_function.test.cpp
• test/library_checker/enumerative_combinatorics/sharp_p_subset_sum.test.cpp
• test/library_checker/enumerative_combinatorics/stirling_number_of_the_second_kind.test.cpp
• test/library_checker/enumerative_combinatorics/stirling_number_of_the_second_kind_fixed_k.test.cpp
• test/library_checker/number_theory/bell_number.test.cpp
• test/library_checker/number_theory/bernoulli_number.test.cpp
• test/library_checker/other/kth_term_of_linearly_recurrent_sequence.test.cpp
• test/library_checker/polynomial/division_of_polynomials.test.cpp
• test/library_checker/polynomial/exp_of_formal_power_series.test.cpp
• test/library_checker/polynomial/inv_of_formal_power_series.test.cpp
• test/library_checker/polynomial/log_of_formal_power_series.test.cpp
• test/library_checker/polynomial/multipoint_evaluation.test.cpp
• test/library_checker/polynomial/polynomial_interpolation.test.cpp
• test/library_checker/polynomial/polynomial_taylor_shift.test.cpp
• test/library_checker/polynomial/pow_of_formal_power_series.test.cpp
• test/library_checker/polynomial/product_of_polynomial_sequence.test.cpp
• test/library_checker/polynomial/sqrt_of_formal_power_series.test.cpp
• test/library_checker/string/wildcard_pattern_matching.test.cpp
• test/yukicoder/yuki_186.test.cpp
• test/yukicoder/yuki_187.test.cpp
• test/yukicoder/yuki_2119.test.cpp
• test/yukicoder/yuki_3022.test.cpp

Code

#pragma once

/**
 * @brief Chinese Remainder Theorem (中国剰余定理)
 * @docs docs/math/crt.md
 */

#include <numeric>
#include <vector>

namespace CRT{
    inline long long mod(long long a, long long m){
        return (a % m + m) % m;
    }

    long long extGCD(long long a, long long b, long long &x, long long &y){
        if(b == 0){
            x = 1;
            y = 0;
            return a;
        }
        long long d = extGCD(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }

    std::pair<long long, long long> chineseRem(const std::vector<long long> &b, const std::vector<long long> &m) {
        long long r = 0, M = 1;
        for(int i = 0; i < (int) b.size(); i++){
            long long p, q;
            long long d = extGCD(M, m[i], p, q);
            if((b[i] - r) % d != 0) return {0, -1};
            long long tmp = (b[i] - r) / d * p % (m[i] / d);
            r += M * tmp;
            M *= m[i] / d;
        }
        r %= M;
        if(r < 0) r += M;
        return {r, M};
    }

    // not coprime
    long long preGarner(std::vector<long long> &b, std::vector<long long> &m, const long long MOD){
        long long res = 1;
        int n = b.size();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                long long g = std::gcd(m[i], m[j]);
                if((b[i] - b[j]) % g != 0) return -1;
                m[i] /= g, m[j] /= g;
                // gcd の分だけ被ってるので振り分ける
                long long gi = std::gcd(m[i], g), gj = g / gi;
                do{
                    g = std::gcd(gi, gj);
                    gi *= g, gj /= g;
                }while(g != 1);
                m[i] *= gi, m[j] *= gj;
                b[i] %= m[i], b[j] %= m[j];
            }
        }
        for(auto x : m) (res *= x) %= MOD;
        return res;
    }

    long long garner(const std::vector<long long> &b, const std::vector<long long> &m, const long long MOD){
        std::vector<long long> tm = m;
        tm.push_back(MOD);
        auto inv = [&](long long a, long long m) -> long long {
            long long x, y;
            extGCD(a, m, x, y);
            return mod(x, m);
        };
        int n = b.size();
        std::vector<long long> coeffs(n + 1, 1), constants(n + 1, 0);
        for(int i = 0; i < n; i++){
            // solve "coeffs[i] * t[i] + constants[i] = b[i] (mod. m[i])
            long long t = mod((b[i] - constants[i]) * inv(coeffs[i], tm[i]), tm[i]);
            for(int j = i + 1; j < n + 1; j++){
                (constants[j] += t * coeffs[j]) %= tm[j];
                (coeffs[j] *= tm[i]) %= tm[j];
            }
        }
        return constants[n];
    }

    // ax + b ≡ 0 (mod m)
    long long modEquation(long long a, long long b, long long m, bool is_positive = false){
        a %= m; b %= m;
        b = (m - b) % m;
        long long g = std::gcd(a, m);
        if(b % g != 0) return -1;
        a /= g; b /= g; m /= g;
        if(is_positive && b == 0){
            return m;
        }
        long long x, y;
        extGCD(a, m, x, y);
        return (b * x % m + m) % m;
    }
}

#line 2 "lib/math/crt.hpp"

/**
 * @brief Chinese Remainder Theorem (中国剰余定理)
 * @docs docs/math/crt.md
 */

#include <numeric>
#include <vector>

namespace CRT{
    inline long long mod(long long a, long long m){
        return (a % m + m) % m;
    }

    long long extGCD(long long a, long long b, long long &x, long long &y){
        if(b == 0){
            x = 1;
            y = 0;
            return a;
        }
        long long d = extGCD(b, a % b, y, x);
        y -= a / b * x;
        return d;
    }

    std::pair<long long, long long> chineseRem(const std::vector<long long> &b, const std::vector<long long> &m) {
        long long r = 0, M = 1;
        for(int i = 0; i < (int) b.size(); i++){
            long long p, q;
            long long d = extGCD(M, m[i], p, q);
            if((b[i] - r) % d != 0) return {0, -1};
            long long tmp = (b[i] - r) / d * p % (m[i] / d);
            r += M * tmp;
            M *= m[i] / d;
        }
        r %= M;
        if(r < 0) r += M;
        return {r, M};
    }

    // not coprime
    long long preGarner(std::vector<long long> &b, std::vector<long long> &m, const long long MOD){
        long long res = 1;
        int n = b.size();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                long long g = std::gcd(m[i], m[j]);
                if((b[i] - b[j]) % g != 0) return -1;
                m[i] /= g, m[j] /= g;
                // gcd の分だけ被ってるので振り分ける
                long long gi = std::gcd(m[i], g), gj = g / gi;
                do{
                    g = std::gcd(gi, gj);
                    gi *= g, gj /= g;
                }while(g != 1);
                m[i] *= gi, m[j] *= gj;
                b[i] %= m[i], b[j] %= m[j];
            }
        }
        for(auto x : m) (res *= x) %= MOD;
        return res;
    }

    long long garner(const std::vector<long long> &b, const std::vector<long long> &m, const long long MOD){
        std::vector<long long> tm = m;
        tm.push_back(MOD);
        auto inv = [&](long long a, long long m) -> long long {
            long long x, y;
            extGCD(a, m, x, y);
            return mod(x, m);
        };
        int n = b.size();
        std::vector<long long> coeffs(n + 1, 1), constants(n + 1, 0);
        for(int i = 0; i < n; i++){
            // solve "coeffs[i] * t[i] + constants[i] = b[i] (mod. m[i])
            long long t = mod((b[i] - constants[i]) * inv(coeffs[i], tm[i]), tm[i]);
            for(int j = i + 1; j < n + 1; j++){
                (constants[j] += t * coeffs[j]) %= tm[j];
                (coeffs[j] *= tm[i]) %= tm[j];
            }
        }
        return constants[n];
    }

    // ax + b ≡ 0 (mod m)
    long long modEquation(long long a, long long b, long long m, bool is_positive = false){
        a %= m; b %= m;
        b = (m - b) % m;
        long long g = std::gcd(a, m);
        if(b % g != 0) return -1;
        a /= g; b /= g; m /= g;
        if(is_positive && b == 0){
            return m;
        }
        long long x, y;
        extGCD(a, m, x, y);
        return (b * x % m + m) % m;
    }
}

Back to top page