逆元的计算方法

问题描述

精选答案

存在取模运算公式：

(a + b) % c = (a % c + b % c) % c

(a * b) % c = (a % c * b % c) % c

(a - b) % c = (a % c - b % c + c) % c

但是不存在取模运算公式:

(a / b) % c = (a % c / b % c) % c

这时候逆元就出现了，逆元就是在mod下，不能直接除以一个数，而是要乘以它的逆元。

我们令inv（b）表示b的逆元，即inv（b） = b ^ -1

那么对于公式 (a / b) % c = (a % c / b % c) % c 我们可以写成乘法取模运算的形式，

可以转化成 (a * inv(b)) % c = (a % c * inv(b) % c) % c, 这样不就合法了。