乘法逆元

如果线性同余方程 $ax\equiv1\pmod b$ ，则 $x$ 称为 $a\bmod b$ 的逆元，记作 $a^{-1}$ 。

参考资料

费马小定理

\begin{align*} & ii^{-1}\equiv 1 \pmod p \\ & ii^{-1}\equiv i^{p-1} \pmod p \\ & i^{-1}\equiv i^{p-2} \pmod p \end{align*}

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

扩展欧几里得

如果 $ax\equiv1\pmod b$ ，说明 $\exists y$ 满足 $ax+by=1$ 。

ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0){x=1;y=0;return a;}
	ll d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}

线性逆元

\begin{align*} & p\bmod i=p-\left\lfloor\dfrac{p}{i}\right\rfloor\cdot i \\ & p\bmod i=-\left\lfloor\dfrac{p}{i}\right\rfloor\cdot i \\ & i^{-1}\cdot(p\bmod i)=-\left\lfloor\dfrac{p}{i}\right\rfloor \\ & i^{-1}=-\left\lfloor\dfrac{p}{i}\right\rfloor(p\bmod i)^{-1} \end{align*}

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

例题

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

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

保证 $p$ 是质数。

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=3000005;
int mod;
ll inv[N];
void init()
{
	inv[1]=1;
	for(int i=2;i<N;i++)
	{
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n>>mod;
	init();
	for(int i=1;i<=n;i++)
	{
		cout<<inv[i]<<'\n';
	}
	return 0;
}

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

求同余方程 $ax\equiv1\pmod b$ 的最小正整数解。（ $a,b\le2\times10^9$ ）

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0){x=1;y=0;return a;}
	ll d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll a,b,x,y;
	cin>>a>>b;
	exgcd(a,b,x,y);
	cout<<(x%b+b)%b<<'\n';
	return 0;
}

参考资料​

费马小定理​

扩展欧几里得​

线性逆元​

例题​

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

洛谷 P1082 [NOIP2012 提高组] 同余方程​