中国剩余定理

参考资料

• 中国剩余定理 - OI Wiki

简介

中国剩余定理 (Chinese Remainder Theorem，CRT) 可求解如下形式的一元线性同余方程组：

$$\begin{cases} x & \equiv a_1 \pmod{n_1} \\ x & \equiv a_2 \pmod{n_2} \\ & \vdots \\ x &\equiv a_k \pmod{n_k} \\ \end{cases}$$

其中 $n_1,n_2,\dots,n_k$ 两两互质。

扩展中国剩余定理（EXCRT）可以解决模数不互质的情况。

例题

洛谷 P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

自从曹冲搞定了大象以后，曹操就开始捉摸让儿子干些事业，于是派他到中原养猪场养猪，可是曹冲满不高兴，于是在工作中马马虎虎，有一次曹操想知道母猪的数量，于是曹冲想狠狠耍曹操一把。举个例子，假如有 $16$ 头母猪，如果建了 $3$ 个猪圈，剩下 $1$ 头猪就没有地方安家了。如果建造了 $5$ 个猪圈，但是仍然有 $1$ 头猪没有地方去，然后如果建造了 $7$ 个猪圈，还有 $2$ 头没有地方去。你作为曹总的私人秘书理所当然要将准确的猪数报给曹总，你该怎么办？

代码（3）

CRT

#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);
	int n;
	cin>>n;
	vector<pair<ll,ll>> a(n);
	__int128 sum=1;
	for(auto &[u,v]:a)
	{
		cin>>u>>v;
		sum*=u;
	}
	__int128 ans=0;
	for(auto [u,v]:a)
	{
		ll k=sum/u;
		auto [g,x,y]=exgcd(k,u);
		ans=(ans+k*x%sum*v%sum+sum)%sum;
	}
	cout<<ll(ans)<<'\n';
	return 0;
}

EXCRT

#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);
	int n;
	cin>>n;
	__int128 ans=0,sum=1;
	while(n--)
	{
		ll a,b;
		cin>>a>>b;
		auto [g,x,y]=exgcd(sum,a);
		ans-=(ans-b)/g*x*sum;
		sum*=a/g;
		ans=(ans%sum+sum)%sum;
	}
	cout<<ll(ans)<<'\n';
	return 0;
}

枚举

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

using ll=long long;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	ll ans=0,sum=1;
	while(n--)
	{
		ll a,b;
		cin>>a>>b;
		while(ans%a!=b)ans+=sum;
		sum*=a;
	}
	cout<<ans<<'\n';
	return 0;
}

洛谷 P4777 【模板】扩展中国剩余定理（EXCRT）

给定 $n$ 组非负整数 $a_i, b_i$，求解关于 $x$ 的方程组的最小非负整数解。

$$\begin{cases} x\equiv b_1\pmod{a_1} \\ x\equiv b_2\pmod{a_2} \\ \dots\\x\equiv b_n\pmod{a_n} \end{cases}$$

代码（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);
	int n;
	cin>>n;
	__int128 ans=0,sum=1;
	while(n--)
	{
		ll a,b;
		cin>>a>>b;
		auto [g,x,y]=exgcd(sum,a);
		ans-=(ans-b)/g*x*sum;
		sum*=a/g;
		ans=(ans%sum+sum)%sum;
	}
	cout<<ll(ans)<<'\n';
	return 0;
}