Skip to content

模运算技巧

加法和乘法

(a+b)%m=((a%m)+(b%m))%m(ab)%m=((a%m)(b%m))%m

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

利用下面转为正数:

(x%m+m)%m

除法取模

这里不引入逆元[1]

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

ab%p=(abp2)%p

注释


  1. 其实就是模为素数时利用费马小定理求得逆元为 bp2  ↩︎

网站基于vitepress主题open17💙