mod計算時の割り算の取り扱い

最近競技プログラミングを始めました。
そこでmod計算中に割り算を使う問題が出題されたところ躓いてしまったので今日復習したところを今後のメモとして残します。
解き方わかったのに残念……

modとは#

主題ではないので簡単に
modとは合同式と言われるもので、もし

$a\equiv b \quad mod \quad m$

とある場合aをmで割ったあまりとbをmで割ったあまりが等しくなることを示しています。
足し算、引き算、かけ算をして回答する場合、mのあまりとして回答をして良いなら計算のどのタイミングでmで割っても答えが変わらない特徴があります。(ただしC++は引き算の時動作が違うため気をつけてください)
例を出すと

$ (13+23) % 5 = (13% 5 +23%5)%5=1$

のような感じです。
なぜこんな計算をするかと言うと、計算する桁が大きくなる時積極的にあまりに置き換えることで計算速度、メモリの側面で良いとのことです。
競技プログラミングでは$10^9+7$で割った余りを出力してください。といった出題のされ方がされました。

割り算の取り扱い#

本題のmod計算時の割り算の取り扱いです。
あまりで回答を出す問題でも割り算を使用することはあります。
そんな時にそのまま計算すると

$3=(9 \div 3)%5 \neq (9%5 \div3%5)%5=4/3 $

などのように成り立ちません。そこで割り算を行う時は割る数（例では３）の逆元をかけることで割り算を行います。

逆元とは##

$9 \div 5$は割り切れない数だが、mod 17と言う条件があると
$9 \div 5 \equiv 12 \quad (mod \quad17)$
が成り立つ。
なぜなら
$12 \times5=60 \equiv9 \quad(mod \quad17)$
が成り立つためです。１から１６に対しても

• $1 \div 5 \equiv 7\quad(mod \quad17)$
• $2 \div 5 \equiv 14\quad(mod \quad17)$
• $3 \div 5 \equiv 4\quad(mod \quad17)$
• $4 \div 5 \equiv 11\quad(mod \quad17)$
• $5 \div 5 \equiv 1\quad(mod \quad17)$
• $6 \div 5 \equiv 8\quad(mod \quad17)$
• $7 \div 5 \equiv 15\quad(mod \quad17)$
• $8 \div 5 \equiv 5\quad(mod \quad17)$
• $9 \div 5 \equiv 12\quad(mod \quad17)$
• $10 \div 5 \equiv 2\quad(mod \quad17)$
• $11 \div 5 \equiv 9\quad(mod \quad17)$
• $12 \div 5 \equiv 16\quad(mod \quad17)$
• $13 \div 5 \equiv 6\quad(mod \quad17)$
• $14 \div 5 \equiv 13\quad(mod \quad17)$
• $15 \div 5 \equiv 3\quad(mod \quad17)$
• $16 \div 5 \equiv 10\quad(mod \quad17)$

この式は最初の
$1 \div 5 \equiv 7\quad(mod \quad17)$ を計算してしまえばあとは
$a \times (1 \div 5) \equiv a \times7%17\quad(mod \quad17)$のようにその数に最初の項をかければ良い。
このようなmod　mに対する$1 \div b $を「mod m に対するbの逆元」といい$b^{-1} $と表記することもあるようです。

ちなみにmod17のにおける１から16までの逆元は

• $1 ^{-1} = 1\quad(mod \quad17)$
• $2 ^{-1} = 9\quad(mod \quad17)$
• $3 ^{-1} = 6\quad(mod \quad17)$
• $4 ^{-1} = 13\quad(mod \quad17)$
• $5 ^{-1} = 7\quad(mod \quad17)$
• $6 ^{-1} = 3\quad(mod \quad17)$
• $7 ^{-1} = 5\quad(mod \quad17)$
• $8 ^{-1} = 15\quad(mod \quad17)$
• $9 ^{-1} = 2\quad(mod \quad17)$
• $10 ^{-1} = 12\quad(mod \quad17)$
• $11 ^{-1} = 14\quad(mod \quad17)$
• $12 ^{-1} = 10\quad(mod \quad17)$
• $13 ^{-1} = 4\quad(mod \quad17)$
• $14 ^{-1} = 11\quad(mod \quad17)$
• $15 ^{-1} = 8\quad(mod \quad17)$
• $16 ^{-1} = 16\quad(mod \quad17)$
  となります。

逆元の求め方#

逆元の求め方はfermatの小定理を用いる方法と拡張ユークリッドの互除法を使うやり方があるそうです。
今回は拡張ユークリッド互除法を用いて求めていきます。
（逆元はaとmが互いに素の時に求めることができる）
$a^{-1}$がmod mの逆元である時
$aa^{-1} \equiv 1 \quad(mod \quad m)$
が成り立ちます。
例）$5 \times 5^{-1} = 5\times 7 = 35\equiv 1\quad(mod \quad17)$

つまり$x=a^{-1}$と置き、適当な数yを用いて
$ax+my=1$
と書くことができます。
このxが求めたい逆元であるためこの一次不定方程式をといて逆元を求めます。
そしてこの一次不定方程式を求める時に使用するものが拡張ユークリッドの互除法です。

早速といていきます。
目標として$ax+my=gcd(a,m)=d$を満たす(x,y)をといていきます。
gcd(a,m)とはaとmの最大公約数です。

まずユークリッドの互除法のようにaをmでわった形
$a=qm+r$

を元の式に代入すると
$(qm+r)x+my=d \quad \Leftrightarrow \quad m(qx+y)+rx$

この時
$s=(qx+y) \quad, t=x$
と置くと

$ms+rt=d$

となり、s、tが分かれば
$x=t \quad,y=s-qt$

と求めることができる。
また、これは最初の式
$ax+my=d$
と同じ形をしているため再帰的に解くことができる。
この拡張ユークリッドの互除法が終わる時は
$dx+0y=d$

となる時（あまりが出なかった時）で、この時の解(x,y)=(1,0)である。
そのためあまりが出なかった時折り返す形で再帰関数を書いていく。
今回はpython3で実装してみました。

euclid.py

# method of euclid
def extGCD(a ,m):
  if(m==0):
    return a,1,0 #a,y,x

  d,s,t = extGCD(m,a%m)
  y=s-(a//m)*t
  x=t
  return d,x,y

def modinv(a,m):
  _,x,_ = extGCD(a,m)
  return x%m

mod_num=17

for i in range(mod_num-1):
  print(str(i+1)+"'s inv ="+str(modinv(i+1,mod_num)))

余談ーーー
s,tとx,yがどっちに入れるのかとても混乱した。
ユークリッドの互除法と同じように”割った数を割ったあまりで割る”、”これをあまりが０になるまで繰り返す”と言うことを意識しておきたい。
逆元はaとmが互いに素の時に求めることができる。逆元を求める時のそのため最大公約数は１となる。

ーーーーー

最後に#

今回は競技プログラミングで躓いたmodの割り算の取り扱いについて勉強してみたことをまとめてみました。
今回見返した時理解できるように書いたつもりですが、参考にしたサイトはとてもわかりやすくてもっと詳しく書いてあるためそちらを見ることをお勧めします。

余談ーーー
拡張ユークリッドの互除法の理解に時間を取られすぎた印象です。
数学的考え方や読解力が欲しい
コツコツ積み重ね頑張っていきます。
ーーーーー

[参考]##

https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a 「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜
https://qiita.com/drken/items/b97ff231e43bce50199a 拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜
https://drken1215.hatenablog.com/entry/2018/06/08/210000 よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方