学过OI，……我便考你一考。逆元的求法，怎样写的？

不能写罢？……我教给你，记着！这些算法应该记着。将来打国赛的时候，写代码要用。

“谁要你教，不是 $a^{-1} \equiv a^{p-2} \pmod{p}$ 么？”

XJ 显出极高兴的样子，将两个指头的长指甲敲着键盘，点头说，“对呀对呀！……求逆元有四种写法，你知道么？”

---

法1：费马小定理

对于指数 $p$，有 $a^{p-1} \equiv 1 \pmod{p}$，故有 $a^{-1} \equiv a^{p-2} \pmod{p}$。

代码：

ll mpow(ll x,ll y)
{
	ll ans=1;
	for(;y;y>>=1,x=x*x%p) if(y&1) ans=ans*x%p;
}
ll inv(ll x)
{
	return mpow(x,p-2);
}

优点：代码简单，速度较快
缺点：仅适合 $p$ 为质数的情况

法2：exgcd

令 $x=a^{-1}$，则 $ax \equiv 1 \pmod{p}$，即 $ax-py=1$，由于 $a,p$ 均为常数，所以可以直接利用 exgcd 算法求出 $x$，注意特判 $x$ 和 $p$ 不互质的情况即可。

代码：

ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b) {x=1,y=0; return a;}
	ll v=exgcd(b,a%b,x,y),t=x-a/b*y;
	x=y,y=t; return v;
}
ll inv(ll x)
{
	ll t1,t2;
	if(exgcd(x,p,t1,t2)!=1) return -1;
	return (t1%p+p)%p;
}

优点：适合所有情况
缺点：代码相比其他方法较繁琐，常数较大

法3：线性求逆元

定义 $a\%b$ 为 $a$ 对 $b$ 取模的值，则由取模的定义有：

$$\lfloor \dfrac{p}x \rfloor x + p \% x=p$$

两边同乘 $x^{-1}(p\%x)^{-1}$ 得：

$$\lfloor \dfrac{p}x \rfloor (p\%x)^{-1} + x^{-1} \equiv px^{-1}(p\%x)^{-1} \equiv 0 \pmod{p}$$

即：

$$x^{-1}=-\lfloor \dfrac{p}x \rfloor (p\%x)^{-1}=(p-\lfloor \dfrac{p}x \rfloor) (p\%x)^{-1}$$

代码：

ll f[N];
void init()
{
	f[1]=1;
	for(int i=2;i<=n;i++) f[i]=(p-p/i)*f[p%i]%p;
}

优点：需要求大量逆元的时候渐进复杂度优于前两种算法
缺点：常数较大；只能求从 $1$ 开始的连续逆元所以只能求到最小质因数 $-1$，因此一般只能用于 $p$ 为质数的情况

法4：线性求任意逆元

令 $a$ 为欲求逆元的数，$n=|a|,A= \prod a_i$，那么：

$$a_x^{-1}=A^{-1} \prod_{i=1}^{x-1}a_i \times \prod_{i=x+1}^n a_i$$

因此，预处理出 $A^{-1}$ 和数组 $a$ 的前后缀积即可线性（$O(n+\log p)$）求出 $a$ 中所有数的逆元。

代码：

int n; ll a[N],b[N],f[N],g[N];
ll inv(ll x) {...}
void work()
{
	f[0]=1; for(int i=1;i<=n;i++) f[i]=f[i-1]*a[i]%p;
	g[n+1]=1; for(int i=n;i>=1;i--) g[i]=g[i+1]*a[i]%p;
	ll tmp=inv(f[n]);
	for(int i=1;i<=n;i++) b[i]=f[i-1]*g[i+1]%p*tmp%p;
}

优点：可以快速求出若干不相关数的逆元，不需要 $p$ 为质数
缺点：

• 只要有一个数不与 $p$ 互质就无法求出任何一个数的逆元
• 还需要一个求单个数逆元的算法，代码较繁琐
• 常数较大

---

XJ 刚打开了电脑，想在 VSC 里打字，见您毫不热心，便又叹一口气，显出极惋惜的样子。

（代码未提交，仅供示意，有错误请联系作者修改）