拡張ユークリッドの互除法
むむむ?この自分の書いた記事、無限に参考にならない気がするが…まあいいや
参考
拡張ユークリッドの互除法とは?
ユークリッドの互除法を活用すると一次不定方程式(5x+7y=31とか)の解の1つが計算できる。
そんな活用法をかっこよく
拡張ユークリッドの互除法
と呼んだりする。
薄い本で擬人化したら強引に拡張されそうなキャラクターとしてのユークリッドちゃんとダイクストラちゃん…
めっちゃどうでもいいけど $ ax + by = c の式のことをベズーの等式と言うらしい。ほぉ…
ax + by = c が整数解を持つ条件とは?
まずユークリッドどうこうの前に、ax + by = c の式が成り立つ条件から考えていきたい。
100x + 10y = 42 が成り立たないのは自明。100円と10円だけで42円は作れないので
ではどういうときにあの式が成り立つのか?
結論から言うと、cはgcd(a,b)の倍数である必要がある(但しa,b,c,x,yは0以外の整数)。gcdは最大公約数のことです…
成り立たない例を挙げると、
$ 21x + 18y = 1 ここで左の21と18はgcd=3でくくれるので…
$ 3(7x + 6y) = 1 こうなる。今回はxとyは整数なので、左辺は3の倍数になってしまい、矛盾してしまう。
「左辺が3の倍数なので右もそうじゃないとおかしい」という考えに至る。
逆に考えるとこの場合、右辺が3の倍数なら、式が成り立つということも分かる。
$ 3(7x + 6y) = 3 (これならできそうなのに…みたいな)
ちなみにこの考えを応用すると、「ax + by = 1 が成り立つとき、aとbが互いに素である」ことも示せるし、
4x+6y=1の整数解がないことも示せる。
つまり「 ax + by = gcd(a,b) × n 」なら成り立つということです。
ユークリッドの互除法で一次不定方程式が解ける理由
比較的雑じゃない説明
前提:ax + by = gcd(a,b) には整数解が存在する。→証明 また34x+29yの例をあげて説明してみる…
この表の左側はユークリッドの互除法をしてるだけで、
https://gyazo.com/6e130f977e3dcede03a318e2fbfb6ffe
この表では、とにかく余りをaとbで表してる。
重要なのは「1 = 34・6 + 29・-7」。最大公約数の1を、34が6つと29が-7つと説明している。
ax + by = gcd(a,b)の整数解が存在することが分かっているので、この6と-7はこの一次不定方程式の整数解となる。
ね、簡単でしょ?(知らんけど)(や、わからん)
もっと雑な説明
主張 : aとbをうまいこと組み合わせたらaとbの最大公約数が作れるらしいぜ!
例えば10と4だったら、10が1つと4が-2つで最大公約数の2が作れる。
でも、なんで?
ユークリッドの互除法を段階で分けていくとします…(謎発想)
34と29(level 0), 29と5(level 1), 5と4(level 2), 4と1(level 3) ←ここで終了
aとb(level n)と表現することにします
level0からlevel1への計算は、「 34 ÷ 29 = 1 あまり 5 」となっています
これは式変形すると「 5 = 34 - 29×1 」という風に表せます
(level n+1)のbは、(level n)のaとbの組み合わせで表せる!
ユークリッドの次のやつが手前のやつで表せるんだったら、再帰的に考えて(?)、最後に出てくるgcd(a,b)も結局aとbの組み合わせで表せるやん!!というのがわかります
めっちゃ雑なまとめ
ユークリッドする時に計算で出てくる余りは今の2つの数字を組み合わせて作ってるので、再帰的に考えたら最後に出てくる最大公約数gcd(a,b)も最初の数字a,bの組み合わせで作れますよね…?
拡張ユークリッドの互除法で高速に逆元を計算する
いや、これは拡張ユークリッドの互除法を直接使う、というわけではないんですが考え方として使うので。
aにxを掛けてMODをとると1になるようなaの逆元xを求めたい。数式で表すと
$ ax \equiv 1 \ (mod \ p)、つまり$ ax + py = 1 の$ xの部分を求めれば良いことがわかります。
$ ax + 1000000007y = 1 ←こういう感じ
改めて、inv…の部分の個人的メモ
pをaで割る式を$ p = qa + r…① とする。ここでqは商(p/a)、rは余り(p%a)である。
ax + py = 1 の両辺をq倍した $ qax + qpy = q …② のqaの部分に、①の式を変形したqa = p - r を代入すると
(p-r)x + qpy = qになって、これを変形すると -rx +px +qpy = qとなって、両辺に-1を掛けてpでくくると
$ rx +p(-x-qy) = -q …③ が得られる。拡張ユークリッドの互除法が使える形になった。
$ rs +pt = 1…④ となるsとtを頑張って求めて、それを-q倍すればいい。式で表すと
$ r(-qs) +p(-qt) = -q…⑤ となる。
③と⑤の左辺を比較すると、$ x = -sq…⑥ であることが分かる(便宜上sとqを入れ替えた)。ここで、
④より、sはrの逆元、かつ①より、rは(q%a)なので、$ s = r^{-1} = (p%$ a)^{-1}
①より、商q = (p/a)
⑥と先ほどの2つより、$ x = -(p%$ a)^{-1} × (p/a)となり、xはax + py = 1よりaの逆元なので、
$ a^{-1} = -(p%$ a)^{-1} × (p/a)
という式が導けます。これをC++っぽく表すと
inv[a] = MOD - inv[MOD%a] * (p/a) % MOD;となる。
ここで、MOD%aは定義より必ずaより小さいので、a=1から順番にDPテーブルを埋めるようにして求めていくことができます。