Linear congruence equation
(Mylib/Number/linear_congruence_equation.cpp)

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

Operations

• linear_congruence_equation(a, b, m)
  • $ax + b = 0 \pmod m$を満たすx($0 \le x \lt m$)を求める。
  • 存在しなければ、std::nulloptを返す。

Requirements

Notes

Problems

References

Depends on

• Mod inverse (Mylib/Number/Mod/mod_inv.cpp)

Code

#pragma once
#include <numeric>
#include <optional>
#include "Mylib/Number/Mod/mod_inv.cpp"

namespace haar_lib {
  // ax + b = 0 (mod m)
  std::optional<int64_t> linear_congruence_equation(int64_t a, int64_t b, int64_t m) {
    if (a >= m) a %= m;
    if (b >= m) b %= m;
    if (a < 0) (a += m) %= m;
    if (b < 0) (b += m) %= m;

    auto g = std::gcd(a, m);
    if (b % g == 0) {
      a /= g;
      b /= g;
      m /= g;
    }

    if (std::gcd(a, m) == 1) {
      return (m - b) * mod_inv(a, m) % m;
    }

    return std::nullopt;
  }
}  // namespace haar_lib

#line 2 "Mylib/Number/linear_congruence_equation.cpp"
#include <numeric>
#include <optional>
#line 2 "Mylib/Number/Mod/mod_inv.cpp"
#include <cstdint>
#include <utility>

namespace haar_lib {
  constexpr int64_t mod_inv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;

    while (b) {
      int64_t t = a / b;
      a -= t * b;
      a = a ^ b;
      b = a ^ b;
      a = a ^ b;

      u -= t * v;
      u = u ^ v;
      v = u ^ v;
      u = u ^ v;
    }

    u %= m;
    if (u < 0) u += m;

    return u;
  }
}  // namespace haar_lib
#line 5 "Mylib/Number/linear_congruence_equation.cpp"

namespace haar_lib {
  // ax + b = 0 (mod m)
  std::optional<int64_t> linear_congruence_equation(int64_t a, int64_t b, int64_t m) {
    if (a >= m) a %= m;
    if (b >= m) b %= m;
    if (a < 0) (a += m) %= m;
    if (b < 0) (b += m) %= m;

    auto g = std::gcd(a, m);
    if (b % g == 0) {
      a /= g;
      b /= g;
      m /= g;
    }

    if (std::gcd(a, m) == 1) {
      return (m - b) * mod_inv(a, m) % m;
    }

    return std::nullopt;
  }
}  // namespace haar_lib

Back to top page