連立線形合同式 (simultaneous linear congruence)
(include/emthrm/math/simultaneous_linear_congruence.hpp)

• View this file on GitHub
• Last update: 2023-02-23 21:59:12+09:00
• Include: #include "emthrm/math/simultaneous_linear_congruence.hpp"

\[A_i x \equiv B_i \pmod{M_i}\]

仕様

名前	戻り値
template <typename T> std::pair<T, T> simultaneous_linear_congruence(const std::vector<T>& a, const std::vector<T>& b, const std::vector<T>& m);	$A_i x \equiv B_i \pmod{M_i}$ を満たす $mk + x$ ($k \in \mathbb{Z},\ 0 \leq x < m$)。ただし存在しないときは $(0, -1)$ を返す。

参考文献

• 秋葉拓哉，岩田陽一，北川宜稔：プログラミングコンテストチャレンジブック [第2版]，pp.261-262，マイナビ出版（2012）

Submissons

https://yukicoder.me/submissions/701737

Depends on

• 逆元 (inverse element) (include/emthrm/math/mod_inv.hpp)

Verified with

• 数学/連立線形合同式 (test/math/simultaneous_linear_congruence.test.cpp)

Code

#ifndef EMTHRM_MATH_SIMULTANEOUS_LINEAR_CONGRUENCE_HPP_
#define EMTHRM_MATH_SIMULTANEOUS_LINEAR_CONGRUENCE_HPP_

#include <numeric>
#include <utility>
#include <vector>

#include "emthrm/math/mod_inv.hpp"

namespace emthrm {

template <typename T>
std::pair<T, T> simultaneous_linear_congruence(const std::vector<T>& a,
                                               const std::vector<T>& b,
                                               const std::vector<T>& m) {
  const int n = a.size();
  T x = 0, md = 1;
  for (int i = 0; i < n; ++i) {
    const T p = md * a[i], q = -x * a[i] + b[i], g = std::gcd(p, m[i]);
    if (q % g != 0) return {0, -1};
    const T m_i = m[i] / g;
    x += md * (q / g * mod_inv(p / g, m_i) % m_i);
    md *= m_i;
  }
  return {x < 0 ? x + md : x, md};
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_SIMULTANEOUS_LINEAR_CONGRUENCE_HPP_

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



#include <numeric>
#include <utility>
#include <vector>

#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/simultaneous_linear_congruence.hpp"

namespace emthrm {

template <typename T>
std::pair<T, T> simultaneous_linear_congruence(const std::vector<T>& a,
                                               const std::vector<T>& b,
                                               const std::vector<T>& m) {
  const int n = a.size();
  T x = 0, md = 1;
  for (int i = 0; i < n; ++i) {
    const T p = md * a[i], q = -x * a[i] + b[i], g = std::gcd(p, m[i]);
    if (q % g != 0) return {0, -1};
    const T m_i = m[i] / g;
    x += md * (q / g * mod_inv(p / g, m_i) % m_i);
    md *= m_i;
  }
  return {x < 0 ? x + md : x, md};
}

}  // namespace emthrm

Back to top page