Chinese remainder theorem
(Mylib/Number/chinese_remainder_algorithm.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

Requirements

Notes

Problems

References

Depends on

• Extended Euclidean algorithm (Mylib/Number/extended_gcd.cpp)

Required by

• Binomial coefficient (Mylib/Combinatorics/binomial_coefficient.cpp)

Verified with

• test/yosupo-judge/binomial_coefficient/main.test.cpp
• test/yukicoder/186/main.test.cpp

Code

#pragma once
#include <cassert>
#include <optional>
#include <vector>
#include "Mylib/Number/extended_gcd.cpp"

namespace haar_lib {
  std::optional<std::pair<int64_t, int64_t>> chinese_remainder_algorithm(
      int64_t b1, int64_t m1,
      int64_t b2, int64_t m2) {
    const auto [d, p, q] = ext_gcd(m1, m2);
    if ((b2 - b1) % d != 0) return std::nullopt;
    const int64_t m = m1 * m2 / d;
    const int64_t t = ((b2 - b1) * p / d) % (m2 / d);
    const int64_t r = (b1 + m1 * t + m) % m;
    return {{r, m}};
  }

  std::optional<std::pair<int64_t, int64_t>> chinese_remainder_algorithm(
      const std::vector<int64_t> &bs,
      const std::vector<int64_t> &ms) {
    assert(bs.size() == ms.size());
    int64_t R = 0, M = 1;
    for (int i = 0; i < (int) bs.size(); ++i) {
      const auto res = chinese_remainder_algorithm(R, M, bs[i], ms[i]);
      if (not res) return std::nullopt;
      const auto [r, m] = *res;
      R                 = r;
      M                 = m;
    }
    return {{R, M}};
  }
}  // namespace haar_lib

#line 2 "Mylib/Number/chinese_remainder_algorithm.cpp"
#include <cassert>
#include <optional>
#include <vector>
#line 2 "Mylib/Number/extended_gcd.cpp"
#include <tuple>

namespace haar_lib {
  auto ext_gcd(int64_t a, int64_t b) -> std::tuple<
      int64_t,  // gcd
      int64_t,  // p
      int64_t   // q
      > {
    if (b == 0) return std::make_tuple(a, 1, 0);
    const auto [d, q, p] = ext_gcd(b, (a + b) % b);
    return std::make_tuple(d, p, q - a / b * p);
  }
}  // namespace haar_lib
#line 6 "Mylib/Number/chinese_remainder_algorithm.cpp"

namespace haar_lib {
  std::optional<std::pair<int64_t, int64_t>> chinese_remainder_algorithm(
      int64_t b1, int64_t m1,
      int64_t b2, int64_t m2) {
    const auto [d, p, q] = ext_gcd(m1, m2);
    if ((b2 - b1) % d != 0) return std::nullopt;
    const int64_t m = m1 * m2 / d;
    const int64_t t = ((b2 - b1) * p / d) % (m2 / d);
    const int64_t r = (b1 + m1 * t + m) % m;
    return {{r, m}};
  }

  std::optional<std::pair<int64_t, int64_t>> chinese_remainder_algorithm(
      const std::vector<int64_t> &bs,
      const std::vector<int64_t> &ms) {
    assert(bs.size() == ms.size());
    int64_t R = 0, M = 1;
    for (int i = 0; i < (int) bs.size(); ++i) {
      const auto res = chinese_remainder_algorithm(R, M, bs[i], ms[i]);
      if (not res) return std::nullopt;
      const auto [r, m] = *res;
      R                 = r;
      M                 = m;
    }
    return {{R, M}};
  }
}  // namespace haar_lib

Back to top page