本文共 1486 字,大约阅读时间需要 4 分钟。
对于正整数和,如果有,那么把这个同余方程中的最小正整数解叫做模的逆元。
如果a|b,想要求a/b%m,a和b非常大除法不容易求,
下面是四种求逆元的方法:
1、如果m为素数,可以根据费马小定理:
{ a是不能被质数m整除的正整数,则有a^(m-1) ≡ 1 (mod m) }
得到逆元为 。推理:
在求a/b%m时,因为b^(m-1)% m = 1,
(A/B)%m=(A/B)*(B^(m-1))%m
=(A* B^(m-2))%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)
例题():
代码:
#include3、用费马小定理和拓展欧几里德求a对于m的逆元时都需要a和m互质,实际上我们还有一种通用的求逆元方法,适合所有情况。公式如下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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!