OMCにおける逆元の計算

OMC（OnlineMathContest）で出題される組合せ分野などの問題において，何らかの素数 $P$ が与えられ， $P$ と互いに素な整数 $x$ に対し $x$ の逆元を求めるという場面がしばしばあります．

$x$ が小さい場合など，容易に逆元が分かる場合も多いですが，そうでない場合は一般的な手法を適用して求めることになると思います．

一般的な手法としてはEuclidの互除法やFermatの小定理を用いる方法が知られていますが，OMC環境では高度な計算機の使用が禁止されているので，計算ミスの温床になります．

本記事では，これらの手法よりも計算ミスを起こしにくいと個人的に思う方法を説明します．

1 方法
2 例
3 補足

方法

基本的なアイデアは次のようになります：

いま，整数 $q$ ， $r$ があって， $P=qx+r$ と書けているとします¹．

このとき， $x^{-1}\equiv-qr^{-1}$ が従います．これにより，逆元を求めるべき対象が $x$ から $r$ に移ります．

これを繰り返して，簡単に逆元が求められるほど小さくなれば，普通に求めて終了するということです．

ここで，通常の割り算の結果を $P=q'x+r'$ とし， $2r'\leq x$ なら $(q,r)=(q',r')$ ，さもなくば $(q,r)=(q'+1,r'-x)$ とします．どちらも， $P=qx+r$ 及び $\left|r\right|\leq\frac x2$ を満たすので，逆元を求める対象は $1$ 回で半分以下になります．

例

$P=1009, x=456$ とします²．このとき，

\begin{aligned} 456^{-1}&\equiv-2\cdot97^{-1}\\ &\equiv2\cdot10\cdot39^{-1}\\ &\equiv-2\cdot10\cdot26\cdot\left(-5\right)^{-1} \end{aligned}

となります．結構小さくなったので，例えばこのあたりで普通に逆元を求めることにします．

$x$ の逆元は， $\frac 1x,\frac{P+1}x,\frac{2P+1}x,\ldots,\frac{(x-1)P+1}x$ のうち唯一ある整数に等しいです．実際にこれらの値を調べることで， $5^{-1}\equiv\frac{1009+1}5=202$ とわかります．

よって， $456^{-1}\equiv2\cdot10\cdot26\cdot202\equiv104$ となります．

補足

この方法の何がいいと思うかを説明します．

一番面倒なのは割り算の商や余りを求めるところだと思いますが，それはEuclidの互除法やFermatの小定理も同じです．

Euclidの互除法と比較すると， $456^{-1}=\ldots$ という言わば本線の式を一本で管理しやすいと思います．もちろん横で， $1009=2\cdot456+97$ 的な式を書いたり電卓を叩いたりしないといけないですが，Euclidの互除法を一回回してから逆順に辿るのよりは楽だと思います．

Fermatの小定理と比較すると，割り算が容易だと思います．OMCで登場する法は精々4桁程度なので， $P$ を $x$ で割ったときに商がいくつになるかというのはある程度見当が付きます．一方， $x^2\bmod P$ がいくつになるかというのは，実際に電卓を叩くまで普通は何もわからないと思います．

次に，マイナスが掛かったり掛からなかったりすることが面倒に見えますが，これは大丈夫です．符号を無視すると $\pm x^{-1}$ が求められ，どちらが求められたかは実際に $x$ を掛けてみれば容易に分かることだからです．

また， $2r'\leq x$ を判定する部分は，半分以下に小さくなることを保証するために必要なだけで，実際にはどちらでもいいです．ぱっと見て微妙ならどちらを選んでも半分に近いということなので，現実的に全く問題ありません．

より一般に， $qx+r\equiv0$ であればよいです． ↩︎
$x$ が合成数なら，素因数分解をすれば簡単な形になる可能性がありますが，今は気にしません． ↩︎