利用费马小定理将除法变为乘法的一个小技巧

本文从WordPress迁移而来, 查看全部WordPress迁移文章

一道cf题目中学到的一个小技巧

1
2
3
4
5
6
7
8
9
(a / b) % m = (a * b^(m-2)) % m , 其a,b和m互质,m是素数

(a * b^(m-2)) % m
= (a * b^(m-1) / b) % m
= ( (a/b) * b^(m-1) ) % m
= ( (a/b) % m * b^(m-1) % m ) % m
由费马小定理可知,b^(m-1) % m = 1
= ( (a/b) % m * 1) % m
= (a / b) % m