跳到主要内容

模逆元

参考资料​

定义​

如果线性同余方程 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⌋⋅ii−1⋅(p mod i)=−⌊pi⌋i−1=−⌊pi⌋(p mod i)−1\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 【模板】模意义下的乘法逆元​

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

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

保证 pp 是质数。

代码（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​

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

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

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

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

答案对 pp 取模。

代码（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 【模板】有理数取余​

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

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

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

代码（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 提高组] 同余方程​

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

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

代码（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;
}