拡張ユークリッドの互除法
通常のユークリッドの互除法
拡張ユークリッドの互除法
2つの整数$ a,bから、$ d=\gcd(a,b)かつ$ d=ax+byとなる整数$ x,yを求める
通常のユークリッドの互除法と何が異なるか
入力$ m,nの最小公倍数$ dだけでなく、$ d=am+bnを満たす$ a,bも同時に求めて、$ d,a,bを返す
行列を用いた解法
ぱっと思い出せれば確実にこっちのほうが計算量も少ないし、計算ミスも少ない
手順
例としてa=96, b=701の最大公約数を求める
1. いつもどおり$ 701=96*7+29の形の式を$ +0になる直前まで求める
2. 行列を作る
$ \left(\begin{array}{cc}{0} & {1} \\ {1} & {-7}\end{array}\right)\left(\begin{array}{c}{701} \\ {96}\end{array}\right)=\left(\begin{array}{l}{96} \\ {29}\end{array}\right).
左側は$ \left(\begin{array}{cc}{0} & {1} \\ {1} & -\mathrm{商}\end{array}\right)
以下のような順番で書くとたぶん速い
https://gyazo.com/a80f69895f20f82fc60c4c6b6aebc8a8→https://gyazo.com/5387bd03244df872ad841247cdc38e5a→https://gyazo.com/5aa6ddc4983f5f6a72d57ee1a230dfe9→https://gyazo.com/fd5f748597e981fb28fa4611a9043120
3. 行列をかけ合わせる
覚えていなくても冷静に考えればわかる
上の画像の最後のようになったとき$ E*D*C*B*A*\left(\begin{array}{c}{701} \\ {96}\end{array}\right)=\left(\begin{array}{c}{1} \\ {0}\end{array}\right)
$ Eに下から一つずつ代入している
このときの右辺の1行目の1が最大公約数
4. 求めたものの1行目が答え
$ E*D*C*B*A=\left(\begin{array}{cc}{-43} & {314} \\ {10} & {-73}\end{array}\right).
となったら、答えは$ (a,b)=(-43,314)
参考
関数型言語での拡張ユークリッドの互除法の実装
引数6つの補助関数を作る
拡張ユークリッドの互除法って2ループ前の変数を保存してないと行けないからこうなるんだなmrsekut.icon
$ \left(\begin{array}{ll}{u_{0}} & {v_{0}} \\ {u_{1}} & {v_{1}}\end{array}\right)=\left(\begin{array}{ll}{1} & {0} \\ {0} & {1}\end{array}\right)
$ \left(\begin{array}{cc}{u_{k}} & {v_{k}} \\ {u_{k+1}} & {v_{k+1}}\end{array}\right)=\left(\begin{array}{cc}{0} & {1} \\ {1} & {-q_{k}}\end{array}\right)\left(\begin{array}{cc}{u_{k-1}} & {v_{k-1}} \\ {u_{k}} & {v_{k}}\end{array}\right) \quad(k>0)
この2式から、$ x_n,u_n,v_nの漸化式とその初期値が求まるので、それを実装に落とし込む
Mathematicaで実装した
code:nb
// an,bnはa_next,b_nextのつもり。
{q, r} = QuotientRemainderm, n; ]
参考
参考
表を作りながら解いて行くと良い