乘法逆元

Veröffentlicht am | in

什么是逆元

所谓逆元是指对于一个二元运算$*$的集合而言，如果$e$是运算的单位远，那么$a*x=e$，就称$x$是$a$的逆元，比如对于加法而言，逆元就是0，对于乘法而言，逆元就是1。
现在这里讨论的是同余关系中的逆元，即$ax\equiv 1(mod m)$，对于给定的$a$，求解$x$。

如何求解

方程$ax\equiv 1(mod m)$其实等同与方程$ax-my=gcd(a,m)$，如此，便可以通过扩展欧几里得求解逆元，同时，这个方法指出有解的前提是$a$与$m$互质。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef long long ll;
ll extendGcd(ll a,ll b,ll &x,ll &y){
	ll ans,t;
	if(b==0){
		x=1;y=0;
		return a;
	}
	ans=extendGcd(b,a%b,x,y);
	t=x;x=y;y=t-(a/b)*y;
	return ans;
}
//返回x，a*x=1(mod m)
ll getInv(ll a,ll m){
	ll x,y,d;
	d=extendGcd(a,m,x,y);
	if(d==1)
		return (x%m+m)%m;
	else
		return -1;
}