专栏文章

题解：P4777 【模板】扩展中国剩余定理（EXCRT）

MMoCaRabbit
P4777题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mionn71j
此快照首次捕获于
2025/12/02 22:09
3 个月前
此快照最后确认于
2025/12/02 22:09
3 个月前
查看原文
这个文章大部分是差不多去年这个时候写的，今天略做修改，上交题解。
CRT 是构造，exCRT 是合并模拟合并同余方程组的过程。
我们先看两个方程的情况。
{x≡a(modp)x≡b(modq)\begin{cases}x \equiv a \pmod p\\x \equiv b\pmod q\end{cases}
转换一下成以下式子。
{k1p+a=xk2q+b=x\begin{cases}k_1p+a=x\\k_2q+b=x\end{cases}
现在要使它变为 kx+b=akx+b=a 的形式。
那相当于 x=k1p+a=k2q+bx=k_1p+a=k_2q+b。
于是 k1p+a=k2q+bk_1p+a=k_2q+b。
移项得 k1p−k2q=b−ak_1p-k_2q=b-a。
首先 p,qp,q 已知，b,ab,a 已知。
那么就解一个不定方程呗！
先使 p,qp,q 互质。
变为 k1p′−k2q′=b−adk_1p'-k_2q'=\frac{b-a}{d}。
现在只有 d∣b−ad|b-a 时有解。
用 exGCD 干就完了。
exGCD 只能求出方程的一组解。
学过一点小奥的就知道，求出一组解 k1′,k2′k_1',k_2'。
通解就是以下式子（证明显然）。
{k1=b−adk1′k2=−b−adk2′\begin{cases}k_1=\frac{b-a}{d}k_1'\\k_2=-\frac{b-a}{d}k_2'\end{cases}
那么 x=k1p+a=a+b−adk1′px=k_1p+a=a+\frac{b-a}{d}k_1'p。
接着，最小解 x′x' 出现了。
那这有什么用呢？
当然。
感性理解一下，所有通解 x≡x′(modlcm⁡(p,q))x \equiv x' \pmod {\operatorname{lcm}(p,q)}
于是，两个方程被合并了。
搞成 x≡a+b−adk1′p(modlcm⁡(p,q))x \equiv a+\frac{b-a}{d}k_1'p \pmod {\operatorname{lcm}(p,q)}。
都是定值。
于是，nn 个方程就被合并为了一个方程 x≡l(modm)x \equiv l \pmod m。
然后 l mod ml \bmod m 最小。
完结撒花。
代码。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int __int128
int exgcd(int a,int b,int &x,int &y){
	int d=0;
	if(b==0){
		x=1,y=0;
		return a;
	}
	else{
		d=exgcd(b,a%b,x,y);
		int p=x;
		x=y,y=p-a/b*y;
	}
	return d;
}
long long n;
int ans,mod; 
signed main() {
	scanf("%lld",&n);
	scanf("%lld%lld",&mod,&ans);
	for(int i=2;i<=n;i++){
		long long a,b;
		scanf("%lld%lld",&a,&b);
		int c,d;
		int p=exgcd(mod,a,c,d);
		if((b-ans)%p){
		    cout<<-1;
		    return 0;
		}
		int lcm=a/p*mod;
		int k=c*(b-ans)/p%(a/p);
		if(k<0) k+=a/p;
		ans=(mod*k+ans)%lcm,mod=lcm;
	}
	printf("%lld",(long long)(ans%mod));
	return 0;
}
正确性在算法讲解里面讲清楚了的。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...