Bézout's identity
(Mylib/Number/bezout_identity.cpp)

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

Operations

$ax + by = c$の形の一次不定方程式を解く。 $c \neq 0 \pmod {gcd(a, b)}$のとき、整数解x, yは存在しない。 そうでなければ、整数解ペアx, yのうちxが最小の非負整数となるものを設定した生成器を返す。

Requirements

Notes

Problems

References

• https://ja.wikipedia.org/wiki/ベズーの等式
• https://mathtrain.jp/axbyc

Depends on

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

Code

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

namespace haar_lib {
  struct bezout_generator {
    int64_t a, b, c, x, y, dx, dy;

    auto value() const { return std::make_pair(x, y); }
    auto next(int64_t n = 1) {
      x += dx * n, y -= dy * n;
      return std::make_pair(x, y);
    }
    auto prev(int64_t n = 1) {
      x -= dx * n, y += dy * n;
      return std::make_pair(x, y);
    }
  };

  std::optional<bezout_generator> bezout_identity(int64_t a, int64_t b, int64_t c) {
    auto [g, x, y] = ext_gcd(a, b);

    if (c % g != 0) return std::nullopt;

    int64_t dx = b / g;
    int64_t dy = a / g;
    int64_t dc = c / g;

    x %= dx;
    if (x < 0) {
      x += std::abs(dx);
    }

    x *= dc;
    dx *= dc;
    dy *= dc;

    y = (c - a * x) / b;

    return bezout_generator({a, b, c, x, y, dx, dy});
  }
}  // namespace haar_lib

#line 2 "Mylib/Number/bezout_identity.cpp"
#include <optional>
#include <utility>
#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 5 "Mylib/Number/bezout_identity.cpp"

namespace haar_lib {
  struct bezout_generator {
    int64_t a, b, c, x, y, dx, dy;

    auto value() const { return std::make_pair(x, y); }
    auto next(int64_t n = 1) {
      x += dx * n, y -= dy * n;
      return std::make_pair(x, y);
    }
    auto prev(int64_t n = 1) {
      x -= dx * n, y += dy * n;
      return std::make_pair(x, y);
    }
  };

  std::optional<bezout_generator> bezout_identity(int64_t a, int64_t b, int64_t c) {
    auto [g, x, y] = ext_gcd(a, b);

    if (c % g != 0) return std::nullopt;

    int64_t dx = b / g;
    int64_t dy = a / g;
    int64_t dc = c / g;

    x %= dx;
    if (x < 0) {
      x += std::abs(dx);
    }

    x *= dc;
    dx *= dc;
    dy *= dc;

    y = (c - a * x) / b;

    return bezout_generator({a, b, c, x, y, dx, dy});
  }
}  // namespace haar_lib

Back to top page