拡張ユークリッドの互除法
(math/extgcd.hpp)
概要
与えられた$a, b$に対して, 最大公約数$gcd(a, b)$と, $ax + by = gcd(a, b)$なる$x, y$を求める.
計算量
$O(\log a)$
使用例
-
extgcd(a, b, x, y)
: $a$と$b$に対して拡張ユークリッドの互除法を行う.
- $ax + by = gcd(a, b)$なる$x, y$は
x
, y
に格納される.
- 返り値 : $gcd(a, b)$
Verified with
Code
Back to top page