Skip to main content

模逆元

Summary

若 ax 模 p 等于 1，则 x 是 a 在模 p 意义下的逆元，记作 a 的负一次方。给出三种求法。快速幂法基于费马小定理，p 为质数时逆元等于 a 的 p−2 次方；扩展欧几里得法解不定方程 ax+py=1 得到逆元，适用于模数与 a 互质的一般情形；线性逆元由 p mod i 的同余变形，推出 i 的逆元关于 (p mod i) 逆元的递推式，在 O(n) 内批量求出前若干个逆元。

参考资料​

定义​

如果线性同余方程 ax≡1(modp)ax\equiv 1\pmod p，则 xx 称为 aa 在模 pp 意义下的 逆元（Inverse），记为 x=a−1x=a^{-1}。

快速幂法​

根据费马小定理（Fermat's Little Theorem）：

aap−2=ap−1≡1(modp)aa^{p-2}=a^{p-1}\equiv 1\pmod p x=ap−2x=a^{p-2}

快速幂：Pow(a,mod-2)。

详见 快速幂。

扩展欧几里得算法​

如果 ax≡1(modp)ax\equiv 1\pmod p，说明存在整数 x,yx,y 满足 ax+py=1ax+py=1。

扩展欧几里得算法：exgcd(a,mod)。

详见 最大公约数。

线性逆元​

p mod i=p−⌊pi⌋⋅ip mod i≡−⌊pi⌋⋅i(modp)i−1⋅(p mod i)≡−⌊pi⌋(modp)i−1≡−⌊pi⌋(p mod i)−1(modp)\begin{aligned} & p\bmod i=p-\left\lfloor\frac{p}{i}\right\rfloor\cdot i \\ & p\bmod i\equiv-\left\lfloor\frac{p}{i}\right\rfloor\cdot i\pmod p \\ & i^{-1}\cdot(p\bmod i)\equiv-\left\lfloor\frac{p}{i}\right\rfloor\pmod p \\ & i^{-1}\equiv-\left\lfloor\frac{p}{i}\right\rfloor(p\bmod i)^{-1}\pmod p \end{aligned}
98 Bcpp
ll inv[N];
void init()
{
	for(int i=1;i<N;i++)
	{
		inv[i]=i==1?1:(mod-mod/i)*inv[mod%i]%mod;
	}
}

例题​

洛谷 P3811 【模板】模意义下的乘法逆元

给定两个整数 n,pn,p，求 1∼n1\sim n 中所有整数在模 pp 意义下的乘法逆元。（n≤3×106,n<p<20000528n\le3\times10^6,n<p<20000528）

保证 pp 是质数。

洛谷 P5431 【模板】模意义下的乘法逆元 2

给定 nn 个正整数 aia_i，求它们在模 pp 意义下的乘法逆元。

由于输出太多不好，所以将会给定常数 kk，你要输出的答案为：

∑i=1nkiai\sum\limits_{i=1}^n\frac{k^i}{a_i}

答案对 pp 取模。

洛谷 P2613 【模板】有理数取余

给出一个有理数 c=abc=\frac{a}{b}，求 c mod 19260817c\bmod 19260817 的值。

这个值被定义为 bx≡a(mod19260817)bx\equiv a\pmod{19260817} 的解。

洛谷 P1082 [NOIP 2012 提高组] 同余方程

求同余方程 ax≡1(modb)ax\equiv1\pmod b 的最小正整数解。（a,b≤2×109a,b\le2\times10^9）