今天我刷题了吗
搜索文档…
逆元

扩展欧几里得法求逆元

1
void exgcd(int a, int b, int& x, int& y)
2
{
3
if (b == 0) {
4
x = 1;
5
y = 0;
6
return;
7
}
8
exgcd(b, a % b, y, x);
9
y -= a / b * x;
10
}
Copied!

快速幂法求逆元

因为
ax1(modb)ax \equiv 1 \pmod b
所以
axab1(modb)ax \equiv a^{b-1} \pmod b
(根据 费马小定理 );
所以
xab2(modb)x \equiv a^{b-2} \pmod b

线性求逆元

求出
1,2,...,n1,2,...,n
中每个数关于
pp
的逆元。
首先,很显然的
111(modp)1^{-1} \equiv 1 \pmod p
然后,设
p=ki+j,j<i,1<i<pp=ki+j,j<i,1<i<p
,再放到
modp\mod p
意义下就会得到:
ki+j0(modp)ki+j \equiv 0 \pmod p
两边同时乘
i1,j1i^{-1},j^{-1}
kj1+i10(modp)kj^{-1}+i^{-1} \equiv 0 \pmod p
i1kj1(modp)i^{-1} \equiv -kj^{-1} \pmod p
i1(pi)(pmodi)1i^{-1} \equiv -(\frac{p}{i}) (p \bmod i)^{-1}
1
inv[i] = 1;
2
for (int i = 2; i <= n; i++) {
3
inv[i] = (ll)(p - p / i) * inv[p % i] % p;
4
}
Copied!
最近更新 11mo ago
复制链接