最大公約数を求める高速なアルゴリズムとしてユークリッドの互除法が知られています。このユークリッドの互除法を拡張することにより、 $$ ax+by=gcd(a,b)$$ の形をした、2変数の一次方程式の整数解を求めることが … 続きを読む 拡張ユークリッドの互除法