【刷题】Modular Multiplicative Inverse 模逆元

模逆元

定义

整数

a

a

a的模逆元是满足

a

⋅

x

acdot x

a⋅x模一个模数

m

m

m等于1。也就是找到一个数

x

x

x:

a

⋅

x

≡

1

     mod m.

a cdot x equiv 1 text{ ~~~~mod m.}

a⋅x≡1     mod m.
也可以把

x

x

x表示为

a

−

1

a^{-1}

a−1

需要注意模逆并不是总是存在。例如，

m

=

4

,

a

=

2

m=4, a=2

m=4,a=2，通过检查m的所有余数，可以很清楚地知道不能找到满足上面等式的

a

−

1

a^{-1}

a−1。当且仅当m和a互质的时候，模逆是存在的。

下面是模拟存在时候找到它们的两种方法，还有一种方法是在线性时间内找到所有数的模逆。

扩展欧几里得算法（Extended Euclidean algorithm)

考虑下面的等式（其中x和y是未知的）

a

⋅

x

+

m

⋅

y

=

1

a cdot x + m cdot y = 1

a⋅x+m⋅y=1

求模逆的代码

pow(a, mod-2, mod)

代码007普通

打赏 收藏 海报 链接