本文共 1486 字，大约阅读时间需要 4 分钟。

对于正整数和，如果有，那么把这个同余方程中的最小正整数解叫做模的逆元。

如果a|b，想要求a/b%m,a和b非常大除法不容易求，

下面是四种求逆元的方法：

1、如果m为素数，可以根据费马小定理:

{

推理：

在求a/b%m时，因为b^(m-1)% m = 1,

（A/B）%m=(A/B)*(B^(m-1))%m

=(A* B^(m-2))%m

代码：

ll quickmod(ll a,ll b,ll mod){	ll ans = 1;	while(b){		if(b & 1)			ans = ans * a % mod;		a = a * a % mod;		b>>=1;	}	return ans;}ans = a % mod * quickmod(b,mod-2,mod) % mod;

2、当a和m互质时，可以用拓展欧几里德定理求。

求a/b%m，先求出b的逆元c：

b*c%m=1，所以b*c + m*y = 1,用拓展欧几里德解方程exgcd(b, m, c, y)求出c即可。

然后a/b%m = a/b%m*(b*c%m)=a*c%m

代码：

exgcd(b, m, c, y);ans = a % mod * (c % mod) %mod;

（其中c求出来可能是个负值，这样的话还需要ans = (ans + mod） % mod）

例题（）：

代码：

#include 
   
    typedef long long ll;#define mod 9973ll exgcd(ll a, ll b, ll &x, ll &y){	ll t, d;	if(b == 0){		x = 1;		y = 0;		return a;	}	d = exgcd(b, a%b, x, y);	t = x;	x = y; 	y = t - a/b*y;	return d;}int main(){	int t;	ll a, b, x, y;	scanf("%d", &t);	while(t--){		scanf("%lld%lld", &a, &b);		ll d = exgcd(b, mod, x, y);		ll ans = (a * x % mod + mod) % mod;		printf("%lld\n", ans);	}	return 0;}
   

现在我们来证明它，已知，证明步骤如下

参考：

4、线性时间求所有逆元

当m是个质数的时候有
inv(a) = (m - m / a) * inv(m % a) % m

证明：

设x = m % a,y = m / a
于是有 x + y * a = m
(x + y * a) % m = 0
移项得 x % m = (-y) * a % m
x * inv(a) % m = (-y) % m
inv(a) = (m - y) * inv(x) % m
于是 inv(a) = (m - m / a) * inv(m % a) % m

代码：

int inv[maxn];inv[1] = 1;for(int i = 2; i < maxn; i++)    inv[i] = (m - m / i) % m * inv[m % i];

转载地址：https://blog.csdn.net/zhj_fly/article/details/76079178 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！