1次不定方程式を解くC++/boostライブラリ

boost の boost/integer/extended_euclidean というライブラリに1次不定方程式を拡張ユークリッド互除法で解く型があるので使ってみます．

1次不定方程式 $mx + ny = \operatorname{gcd}(m, n)$ の解 $x, y$ を1つ求めることができます．

以下のプログラムをatcoder の C++(GCC9.2.1) で実行します．

プログラム

#include <iostream>
#include <boost/integer/extended_euclidean.hpp>
using namespace std;

int main() {
  
  auto res = boost::integer::extended_euclidean(12, 15);

  cout << res.gcd << " " << res.x << " " << res.y  << "\n";

  return 0;
}

出力

3 -1 1

参考

Extended Euclidean Algorithm - 1.72.0