【蓝桥杯】Python算法——求逆元的两种算法

零、前言

距离25年蓝桥杯还有大概三个月时间，接下来重点应该会放在蓝桥杯备考方向，一起努力，一起加油

一、逆元

什么是逆元？这是数论中的一个基本概念。如果存在$$ax\equiv 1(modn)$$则$x$为$a$在模$n$意义下的逆元。可以简单地理解为，求一个$x$使得$axmodn=1$
逆元的意义在哪呢？如果遇到需要求$a/bmodn$的情况，则可以转化为分子a乘以分母b的逆元的形式，这样我们将除法转化为乘法，提高了计算效率。

二、扩展欧几里得算法

那么怎么求解逆元呢？由前面给出的公式$ax\equiv 1(modn)$，不难看出求逆元$x$就是求解等式的解：$$ax+ny=1$$因为$(ax+ny)modn=axmodn$,求出了$x$和$y$，那么$x$就是$a$的逆元。
为了方便推导，我们暂时把$n$换成$b$，等号右边换位$m$，求解的更一般的形式。$$ax+by=m$$根据裴蜀定理：对于任意整数$a$,$b$,$m$，求解未知整数$x$,$y$时，必须满足$gcd(a,b)|m$，即$m$是$gcd(a,b)$的倍数时才有解。
所以我们将计就计，如果$m$是$gcd(a,b)$的一倍，也就是$m=gcd(a,b)$，先解出方程$ax+by=gcd(a,b)$的解$x_1$,$y_1$,然后两边乘以$m/gcd(a,b)$，不就能求出来我们想要的了吗？$$a\frac{m{x}_1}{gcd(a,b)}+b\frac{m{y}_1}{gcd(a,b)}=m$$所以，我们进一步研究问题：解出方程$ax+by=gcd(a,b)$的解。
那么我们需要求出三个东西，$x$，$y$，$gcd(a,b)$，这就是扩展欧几里得算法的根本研究问题。（By the way，欧几里得算法就是求解$gcd(a,b)$，方法就是我们熟知的辗转相除法。）
当$b=0$，有特解$x=1,y=0$，这是迭代的初始条件。
当$b\ne 0$，假设$x_1$，$y_1$是 $a{x}_1+b{y}_1=gcd(a,b)$的解，根据欧几里得算法：$gcd(a,b)=gcd(b,amodb)$,下一步我们构造$b{x}_2+(amodb)y_2=gcd(b,amodb)$,
那$amodb$怎么表示？不就是$a/b$的余数嘛，所以你细品：a%b = a - (a//b)*b，($a÷b=q\dots \dots r$，则$a=b\ast q+r$,其中q就是a整除b的结果a//b)， 带入到上式则有$b{x}_2+(amodb)y_2=b{x}_2+(a-(a//b)b)y_2=gcd(b,amodb)$
好乱，整理一下：
$$\{\begin{array}{rl}a{x}_1+b{y}_1& =gcd(a,b)\\ b{x}_2+(a-(a//b)b)y_2& =gcd(b,amodb)\\ gcd(a,b)& =gcd(b,amodb)\end{array}$$这样我们就能找到$(x_1,y_1)$和$(x_2,y_2)$的关系了：$a{x}_1+b{y}_1=a{y}_2+b(x_2-(a//b)y_2)$，所以有$$\{\begin{array}{rl}{x}_1& =y_2\\ y_1& =x_2-(a//b)y_2\end{array}$$这就是递归的关系式。
有了初始值与递归关系，就可以写代码来求解了。

def exgcd(a,b):
	if b==0:
		return a,1,0
	gcd,x2,y2 = exgcd(b,a%b)
	x1,y1 = y2,x2-(a//b)*y2
	return gcd,x1,y1

别忘了我们求的是$ax+by=gcd(a,b)$，而我们要求的是$ax+by=m$，那么对于函数输出，还要再乘以$m/gcd$

def Func(a,b,m):
	gcd,x1,y1 = exgcd(a,b)
	if m % gcd != 0:return None,None,None
	x0, y0 = x * m // gcd, y * m // gcd
	return gcd, x0, y0

汇总：

def exgcd(a,b):
	if b==0:
		return a,1,0
	gcd,x2,y2 = exgcd(b,a%b)
	x1,y1 = y2,x2-(a//b)*y2
	return gcd,x1,y1
	
def Func(a,b,m):
	gcd,x1,y1 = exgcd(a,b)
	if m % gcd != 0:return None,None,None
	x0, y0 = x * m // gcd, y * m // gcd
	return gcd, x0, y0

MOD = 1e9+7
a = int(input())
_, inv_a, _ = Func(a, MOD, 1)
print(inv_a)

三、费马小定理

费马小定理：
如果$p$是素数，且$a$是一个不能被$p$整除的整数，那么：$$a^{p-1}\equiv 1(\mathrm{mod}p)$$

这给了我们一个求逆元的好方法：$$a{a}^{p-2}\equiv 1(modp)$$注意前提：模数为素数，且$a$不能被$p$整除。
这时我们只需要算一下$a^{p-2}$就行了，很方便吧。可以用快速幂来求。

def KSM(a, b, mod):
	if b == 0: return 1
	if b == 1: return a % mod
	res = KSM(a, b//2, mod)
	res = res * res % mod
	if b % 2 == 1:
		res = res * a % mod
	return res

def INV(a):
	return KSM(a, MOD-2, MOD)

MOD = 1e9+7
a = int(input())
print(INV(a))

四、总结

介绍了两种方法求解逆元：扩展欧几里得算法和费马小定理算法，前者实用性广，而后者有一个前提，即模数必须为素数，不过一般用费马小定理的情况要多一些。