拡張ユークリッドの互除法
説明
$m, n$ の最大公約数を $\gcd(m, n)$ とする。ここでは整数 $m, n$ が与えられたとき, 拡張ユークリッドの互除法を用いて $mx + ny = \gcd(m, n)$ の解となる整数 $x, y$ を求める。
計算量
クエリ $O(\log n)$
実装例
$m, n$ の最大公約数を $\gcd(m, n)$ とする。ここでは整数 $m, n$ が与えられたとき, 拡張ユークリッドの互除法を用いて $mx + ny = \gcd(m, n)$ の解となる整数 $x, y$ を求める。
クエリ $O(\log n)$