模逆元

参考资料

• 模逆元 - OI Wiki
• 【笔记】常见逆元计算方法总结 - 洛谷专栏

定义

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

快速幂法

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

$$aa^{p-2}=a^{p-1}\equiv 1\pmod p$$ $$x=a^{p-2}$$

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

详见 快速幂。

扩展欧几里得算法

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

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

详见 最大公约数。

线性逆元

$$\begin{aligned} & p\bmod i=p-\left\lfloor\frac{p}{i}\right\rfloor\cdot i \\ & p\bmod i=-\left\lfloor\frac{p}{i}\right\rfloor\cdot i \\ & i^{-1}\cdot(p\bmod i)=-\left\lfloor\frac{p}{i}\right\rfloor \\ & i^{-1}=-\left\lfloor\frac{p}{i}\right\rfloor(p\bmod i)^{-1} \end{aligned}$$

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,p$，求 $1\sim n$ 中所有整数在模 $p$ 意义下的乘法逆元。（$n\le3\times10^6,n<p<20000528$）

保证 $p$ 是质数。

Code (1)

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

using ll=long long;
const int N=3000005;
int mod;
ll inv[N];
void init()
{
	for(int i=1;i<N;i++)
	{
		inv[i]=i==1?1:(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;
}

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

给定 $n$ 个正整数 $a_i$，求它们在模 $p$ 意义下的乘法逆元。

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

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

答案对 $p$ 取模。

Code (1)

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

using ll=long long;
const int N=5000005;
int mod;
ll Pow(ll x,ll y)
{
	x%=mod;
	ll res=1;
	while(y)
	{
		if(y&1)res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
ll a[N],p[N],q[N];
int read()
{
	int x=0,f=1;char c=getchar_unlocked();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar_unlocked();}
	while(c>='0'&&c<='9')x=x*10+c-48,c=getchar_unlocked();
	return x*f;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,k;
	n=read();mod=read();k=read();
	for(int i=1;i<=n;i++)a[i]=read();
	p[0]=q[n+1]=1;
	for(int i=1;i<=n;i++)p[i]=p[i-1]*a[i]%mod;
	for(int i=n;i>=1;i--)q[i]=q[i+1]*a[i]%mod;
	ll inv=Pow(p[n],mod-2),ans=0,cur=k;
	for(int i=1;i<=n;i++)
	{
		ans=(ans+cur*inv%mod*p[i-1]%mod*q[i+1]%mod)%mod;
		cur=cur*k%mod;
	}
	cout<<ans<<'\n';
	return 0;
}

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

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

这个值被定义为 $bx\equiv a\pmod{19260817}$ 的解。

Code (1)

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

using ll=long long;
const int mod=19260817;
ll read()
{
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x*10+c-48)%mod;c=getchar();}
	return x*f;
}
ll Pow(ll x,ll y)
{
	x%=mod;
	ll res=1;
	while(y)
	{
		if(y&1)res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll a=read(),b=read();
	if(b==0)cout<<"Angry!"<<'\n';
	else cout<<a*Pow(b,mod-2)%mod<<'\n';
	return 0;
}

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

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

Code (1)

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

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