扩展欧几里德法求逆元

欧几里德法

首先不妨了解了解欧几里德法。
欧几里德法是用来求最大公约数的,有辗转相减法和辗转相除两种,两种本质其实是一样的。但是在执行效率上是不同的。在普通数据中趋向于辗转相减法,然而在大数中,辗转相减的效率会因为避免取模运算而高于辗转相除法。这里用 Gcd(a,\ b) 来表示公约数,且约定所有的数都是整数。公式如下:

Gcd(a,\ b)\ =\ Gcd(b,\ a\ -\ b)

Gcd(a,\ b)\ =\ Gcd(b,\ a\ \%\ b)

边界条件为 Gcd(a,\ 0)\ =\ a 但通常在 ab 的倍数时候就可以退出递归了,当然也有高效一点的非递归版。
至于证明的话,主要是反证法证明,大家可以自己想一想,实在不行还有搜索引擎。
下面直接上代码:

关于扩展欧几里得

扩展欧几里得法是用来求这样一类方程的某个解的。

ax\ +\ by\ =\ Gcd(a,\ b)


下面我们尽量去推导一下这种方法的过程。
其实仿造辗转相除法,我们可以得到这样一个式子

bx\ +\ (a\ \%\ b)y\ =\ Gcd(b,\ a\ \%\ b)


而且有一点是,在 b\ =\ 0 的时候 ax\ +\ by\ =\ Gcd(a,\ b) 有一组解
 \left\{\begin{aligned}x\ =\ 1 \\y\ =\ 0 \\\end{aligned}\right.
更重要的是,我们知道 Gcd(b,\ a\ \%\ b)\ =\ Gcd(a,\ b)
为了方便,我们不令 a\ =\ kb + c ,如果我们知道 bx\ +\ (a\ \%\ b)y\ =\ Gcd(b,\ a\ \%\ b) 的解也就是 bx\ +\ cy\ =\ Gcd(a,\ b) 的解
就是这样一组方程组

 \left\{\begin{aligned}ax_1\ +\ by_1\ =\ Gcd(a,\ b)\\bx\ +\ cy\ =\ Gcd(a,\ b)\\\end{aligned}\right.


我们带入一些已知条件得

 \left\{\begin{aligned}b(kx_1+y_1)\ +\ cx_1\ =\ Gcd(a,\ b)\\bx\ +\ cy\ =\ Gcd(a,\ b)\\\end{aligned}\right.


可以看出其中一组解 \left\{\begin{aligned}x\ =\ kx_1+y_1 \\y\ =\ x_1 \\\end{aligned}\right.
化简得 \left\{\begin{aligned}x_1\ =\ y \\y_1\ =\ x\ -\ ky \\\end{aligned}\right.
OK,有了这个,我们就能通过下一个方程的一组解退出上一个方程的一组解,已此类推,可以通过递归得到原方程的一组解。
代码如下:

利用上面的方法求逆元

当然,这种方法的条件食 a b 互质,也就是说Gcd(a,\ b)\ =\ 1,就有这样的方程

ax\ +\ by\ =\ 1


两边同对 b 取模,则得到

ax\ \equiv\ 1\ (Mod\ b)


移项得

x\ \equiv\ a^{-1}\ (Mod\ b)


也就是说 xa 在模 b 的逆元。所以说,扩展欧几里德法求得的 x 就是逆元。
NOIP2012提高组其中一题就是裸的扩展欧几里德,题目见这里
直接上代码

复杂度

其实不管是辗转相除还是辗转相减。复杂度都是接近于,O(\log n)

其他

扩欧求逆元其实也有局限性,就是保证两个数要互质,当然如果模的数是素数的话就不用担心这么多了。在求逆元的时候还要自己选择。

完结

发表评论

电子邮件地址不会被公开。 必填项已用*标注