模运算技巧

加法和乘法

$$(a+b)\mathrm{\%}m=((a\mathrm{\%}m)+(b\mathrm{\%}m))\mathrm{\%}m$$$$(a\ast b)\mathrm{\%}m=((a\mathrm{\%}m)\ast (b\mathrm{\%}m))\mathrm{\%}m$$

负数取模处理(减法注意事项)

利用下面转为正数:

$$(x\mathrm{\%}m+m)\mathrm{\%}m$$

除法取模

这里不引入逆元^[1]

当$p$为素数,a为b的倍数,b不是p的倍数(b,p互质),则有:

$$\frac{a}{b}\mathrm{\%}p=(a\ast b^{p-2})\mathrm{\%}p$$

注释

---

1. 其实就是模为素数时利用费马小定理求得逆元为$b^{p-2}$ ↩︎