sky’s 雑記

主にAndroidとサーバーサイドの技術について記事を書きます

モジュラ逆数(逆元)と組み合わせ

モジュラ逆数 逆元 AtCoder 組み合わせ 整数

競技プログラミングでよく見る 10^{9}+7の余りを出力せよについて, 初めの頃(今も初めの頃ではある...)は32bit,64bitに収まらないから大きめの自然数で割るくらいにしか考えていなかったが組み合わせを求める問題でより深い理解が必要になったのでまとめる.

導入

以下のように組み合わせを階乗で表現できることは高校数学をやっていれば知っていると思う.

_{n}C_r =\displaystyle \frac{_{n}P_{r}}{r!} = \displaystyle \frac{n!}{r!(n-r)!}

問題は \displaystyle \frac{n!}{k!(n-k)!}\pmod {10^{9}+7}をどう計算するかである.

合同式の性質について加/減/乗については数値計算と同様に直感的に行って良く,

a ≡ p{\pmod {r}}, b ≡ q{\pmod {r}}

a+b ≡ p+q{\pmod {r}} \\ a-b ≡ p-q {\pmod {r}} \\ a*b ≡ p*q{\pmod {r}}

だが割り算についてはこれは成り立たない.

\displaystyle \frac{a}{b} !≡ \displaystyle \frac{p}{q}{\pmod {r}}

今回の記事はこれをどう解決するかという話.

合同式と除算

割り算は-1乗すれば掛け算に変換できるので以下のようにする. _{n}C_r = n!*(k!)^{-1}*((n-k)!)^{-1}

一旦話をわかりやすくするために以下について考える.

\displaystyle \frac{a}{b} = a*b^{-1}

ここで問題になるのがrの法のもとで b^{-1} はいくつになるかということなのだがまず定義を見てみる.

rの法のもとで bとの積の余りが1になるような b^{-1}のことを逆元やモジュラ逆数といい,

b*b^{-1}≡1\pmod {r}

またモジュラ逆数が存在するための必要十分条件は対象の整数と法が互いに素であり

b*b^{-1}≡1\pmod {r} <-> gcd(b,r) = 1

となる.

モジュラ逆数を求めるアルゴリズム

競技プログラミングで逆元の求め方を調べると主に2つあり

フェルマーの小定理

p を素数とし、a を p の倍数でない整数（a と p は互いに素）とするときに、

\displaystyle a^{p-1} ≡ 1{\pmod {p}} \\ \displaystyle a*a^{p-2} ≡ 1{\pmod {p}}

となりaの逆元は a^{p-2} となる. 競技プログラミングではpは 10^{9}+7であり素数なのでこちらで事足りることが多い.

拡張ユークリッド互除法

逆元以外にも応用範囲が広く整数問題の理解にも繋がる気配を感じるのでこちらにも触れておく.

ユークリッド互除法は整数の最大公約数を求めるもので,aとbの最大公約数がcとすると以下のように表される.

gcd(a,b) = c

拡張ユークリッド互除法は以下の一次不定方程式の解x,yとcを同時に定める手法であり,

ax+by = c

モジュラ逆数の定義で以下のように述べたので拡張ユークリッド互除法を適用することができ, 逆元を求めるには

gcd(r,a) = 1 <-> rs+at = 1

例として (m,a)=(29,12)について考えてみると, 29s+12t = 1 を満たすs,tを求めれば良く,

初期条件として以下は明らか.

(r_{0},s_{0},t_{0}) = (29, 1, 0) \\ (r_{1},s_{1},t_{1}) = (12, 0, 1)

また

s_{i+1} = s_{i-1}-s_{i}*q_{i}, r_{i+1} = r_{i-1}-r_{i}*q_{i}

より

(r_{2},s_{2},t_{2}) = (5, 1, -2)\\ (r_{3},s_{3},t_{3}) = (2, -2, 5)\\ (r_{4},s_{4},t_{4}) = (1, 5, -12)

最終的に以下が求まる.

1 = 5*29-12*12

式を変形すると

-12*12-1 = 5*29

であり

-12*12-1は 29の倍数と解釈できるので -12*12-1≡0 \pmod {29}である.

また合同式の性質から -12*12 \pmod {29} - 1 \pmod {29} ≡ 0 \pmod {29}であり -12*12≡1が導かれる.

よって12の逆元は -12+29nとなる.

以上のことから組み合わせを 10^{9}+7で割った余りは以下の式を計算すれば良いとわかる.

_{n}C_r\pmod {10^{9}+7} ≡ n!\pmod {10^{9}+7}*(r!)^{-1}\pmod {10^{9}+7}*((n-r)!)^{-1}\pmod {10^{9}+7}

refs

筑波大の先生の動画がこの記事を書くにあたって理解の助けになって大変感謝である.

www.youtube.com

www.youtube.com

3 ÷ 4 ≡ 9 mod 11を計算するのに必要なモジュラ逆数を理解する - Never Too Late

RSA暗号の解説に出てくる数値の逆数のmod | なたで日記