class="markdown_views prism-atelier-sulphurpool-light">

• 引入
• 逆元
  • 概念
  • 求逆元
  • 用法
• 例题

引入

通常情况下，模运算有加法、乘法，减法的分配率，即：
(a+b)%m=(a%m+b%m)%m" role="presentation">(a+b)%m=(a%m+b%m)%m$(a+b)\mathrm{\%}m=(a\mathrm{\%}m+b\mathrm{\%}m)\mathrm{\%}m$
(a−b)%m=(a%m−b%m)%m" role="presentation">(a−b)%m=(a%m−b%m)%m$(a-b)\mathrm{\%}m=(a\mathrm{\%}m-b\mathrm{\%}m)\mathrm{\%}m$
(a×b)%m=(a%m×b%m)%m" role="presentation">(a×b)%m=(a%m×b%m)%m$(a\times b)\mathrm{\%}m=(a\mathrm{\%}m\times b\mathrm{\%}m)\mathrm{\%}m$
（模运算为最高级运算，负数不考虑= =）
但是有除法怎么办？显然ab%m≠a%mb%m" role="presentation">ab%m≠a%mb%m${\displaystyle \frac{a}{b}}\mathrm{\%}m\ne {\displaystyle \frac{a\mathrm{\%}m}{b\mathrm{\%}m}}$，需要用逆元将其变为乘法，然后使用分配率。

逆元

概念

若ab≡1 (mod m)" role="presentation">ab≡1 (mod m)$ab\equiv 1(modm)$,则称a" role="presentation">a$a$与b" role="presentation">b$b$在模m" role="presentation">m$m$的情况下互为逆元。
记b=a−1" role="presentation">b=a−1$b=a^{-1}$，所以b" role="presentation">b$b$又叫a" role="presentation">a$a$的数论倒数。

求逆元

需要用到费马小定理：若p" role="presentation">p$p$为质数（显然a" role="presentation">a$a$与p" role="presentation">p$p$互质），则ap−1≡1 (mod p)" role="presentation">ap−1≡1 (mod p)$a^{p-1}\equiv 1(modp)$，所以ap−2" role="presentation">ap−2$a^{p-2}$就是a" role="presentation">a$a$在模p" role="presentation">p$p$的情况下的一个逆元，由模乘法的分配率得ap−2%m" role="presentation">ap−2%m$a^{p-2}\mathrm{\%}m$也是a" role="presentation">a$a$的一个逆元，用快速幂求得即可（一般题目中的模数都是质数）。

用法

设c=b−1" role="presentation">c=b−1$c=b^{-1}$，则bc%m=1" role="presentation">bc%m=1$bc\mathrm{\%}m=1$（m" role="presentation">m$m$不可能为1" role="presentation">1$1$），所以有：ab%m=ab∗1%m=ab×bc%m=ac%m=a·b−1%m" role="presentation">ab%m=ab∗1%m=ab×bc%m=ac%m=a⋅b−1%m$${\displaystyle \frac{a}{b}}\mathrm{\%}m={\displaystyle \frac{a}{b}}\ast 1\mathrm{\%}m={\displaystyle \frac{a}{b}}\times bc\mathrm{\%}m=ac\mathrm{\%}m=a·b^{-1}\mathrm{\%}m$$
求出b" role="presentation">b$b$的逆元就能处理模运算中的除法了。

例题

AtCoder - 1974·いろはちゃんとマス目 / Iroha and a Grid