数学/中国剰余定理
(test/math/chinese_remainder_theorem.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: https://yukicoder.me/problems/no/186

Depends on

• 中国剰余定理 (Chinese remainder theorem) (include/emthrm/math/chinese_remainder_theorem.hpp)
• 逆元 (inverse element) (include/emthrm/math/mod_inv.hpp)

Code

/*
 * @title 数学/中国剰余定理
 *
 * verification-helper: PROBLEM https://yukicoder.me/problems/no/186
 */

#include <iostream>
#include <vector>

#include "emthrm/math/chinese_remainder_theorem.hpp"

int main() {
  constexpr int N = 3;
  std::vector<long long> x(N), y(N);
  for (int i = 0; i < N; ++i) {
    std::cin >> x[i] >> y[i];
  }
  const auto [ans, mod] = emthrm::chinese_remainder_theorem(x, y);
  if (mod == 0) {
    std::cout << "-1\n";
  } else {
    std::cout << (ans == 0 ? mod : ans) << '\n';
  }
  return 0;
}

#line 1 "test/math/chinese_remainder_theorem.test.cpp"
/*
 * @title 数学/中国剰余定理
 *
 * verification-helper: PROBLEM https://yukicoder.me/problems/no/186
 */

#include <iostream>
#include <vector>

#line 1 "include/emthrm/math/chinese_remainder_theorem.hpp"



#include <numeric>
#include <utility>
#line 7 "include/emthrm/math/chinese_remainder_theorem.hpp"

#line 1 "include/emthrm/math/mod_inv.hpp"



#line 6 "include/emthrm/math/mod_inv.hpp"

namespace emthrm {

long long mod_inv(long long a, const int m) {
  if ((a %= m) < 0) a += m;
  if (std::gcd(a, m) != 1) return -1;
  long long x = 1;
  for (long long b = m, u = 0; b > 0;) {
    const long long q = a / b;
    std::swap(a -= q * b, b);
    std::swap(x -= q * u, u);
  }
  x %= m;
  return x < 0 ? x + m : x;
}

}  // namespace emthrm


#line 9 "include/emthrm/math/chinese_remainder_theorem.hpp"

namespace emthrm {

template <typename T>
std::pair<T, T> chinese_remainder_theorem(std::vector<T> b, std::vector<T> m) {
  const int n = b.size();
  T x = 0, md = 1;
  for (int i = 0; i < n; ++i) {
    if ((b[i] %= m[i]) < 0) b[i] += m[i];
    if (md < m[i]) {
      std::swap(x, b[i]);
      std::swap(md, m[i]);
    }
    if (md % m[i] == 0) {
      if (x % m[i] != b[i]) return {0, 0};
      continue;
    }
    const T g = std::gcd(md, m[i]);
    if ((b[i] - x) % g != 0) return {0, 0};
    const T u_i = m[i] / g;
    x += (b[i] - x) / g % u_i * mod_inv(md / g, u_i) % u_i * md;
    md *= u_i;
    if (x < 0) x += md;
  }
  return {x, md};
}

}  // namespace emthrm


#line 11 "test/math/chinese_remainder_theorem.test.cpp"

int main() {
  constexpr int N = 3;
  std::vector<long long> x(N), y(N);
  for (int i = 0; i < N; ++i) {
    std::cin >> x[i] >> y[i];
  }
  const auto [ans, mod] = emthrm::chinese_remainder_theorem(x, y);
  if (mod == 0) {
    std::cout << "-1\n";
  } else {
    std::cout << (ans == 0 ? mod : ans) << '\n';
  }
  return 0;
}

Back to top page