中国剩余定理（CRT）学习小结

FishWang

发布于 2025-08-26 15:09:55

2160

①设正整数

两两互素，则同余方程组

有整数解。并且在模

下的解是唯一的，解为

其中

，而

为

模

的逆元。

代码如下：

__int64 GCD(__int64 a,__int64 b)
{
	return b == 0 ? a : GCD(b,a%b);
}
void exGCD(__int64 a,__int64 b,__int64 &x,__int64 &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return;
	}
	exGCD(b,a%b,y,x);
	y -= a / b * x;
}
__int64 CRT(int *m,int *a,int n)		//m表示除数，a为余数 
{
	__int64 M = 1;
	for (int i = 1 ; i <= n ; i++)
		M = M / GCD(M , m[i]) * m[i];		//这里求最小公倍数
	__int64 ans = 0;
	__int64 x,y;
	for (int i = 1 ; i <= n ; i++)
	{
		__int64 Mi = M / m[i];
		exGCD(m[i],Mi,x,y);		//求 Mi 模 m[i] 的逆元（即公式的 M^(-1)） 
		ans = (ans + a[i] * Mi * y) % M;
	}
	return ans;
}

②当m不互质：（转载至：点击打开链接）

中国剩余定理：

给定方程组:

x%a[0] = m[0]

x%a[1] = m[1]

···

x%a[n-1] = m[n-1]

求变量x 的值

m必须互质

当m不互质时用合并方程的做法：

（合并方程的原因：当我们把n条方程合并成1条时就是extend能求的了，extend能求一条方程的解

问题描述：给出bi，ni的值，且n1, n2, n3,…, ni两两之间不一定互质，求Res的值？ 解：采用的是合并方程的做法。 这里将以合并第一第二个方程为例进行说明 由上图前2个方程得(设k1、k2为某一整数)：

所以我们简化一下结论：

已知方程组（b1,b2,n1,n2是已知量）：

res%b1 = n1

res%b2 = n2

合并两条方程得到：

res % ( (n1*n2)/d ) = b1+n1*( K%(n2/d))

其中K = (k1*(b2-b1)/d) % (n2/d);

其中d = gcd(n1,n2);

其中k1：

k1*n1 - k2*n2 = b2-b1

k1,d 可以直接由extend_gcd得到 extend_gcd(n1,n2,d,k1,k2);

(b2-b1)%d == 0 说明extend跑出的k1是一个解，否则说明不存在满足解的k1

注意求K时：为了得到最小非负整数K，所以用一个取模的技巧

K = (K%mod+mod)%mod;

例题及题解：点击打开链接

==================================

若 a == b (mod n)

能推出下面2条等式

1： (a+c) == b+c (mod n)

2：ac == bc (mod n) （但 ac==bc(mod n) 不能推出 a==b(mod n)）

代码实现：（确实不好记，下面的代码我更新了好几遍，每次都有小错误）

__int64 GCD(__int64 a , __int64 b)
{
	return b == 0 ? a : GCD(b,a%b);
}
__int64 exGCD(__int64 a,__int64 b,__int64 &x,__int64 &y)
{
	if (!b)
	{
		x = 1;
		y = 0;
		return a;
	}
	int g = exGCD(b,a%b,y,x);
	y -= a / b * x;
	return g;
}
__int64 CRT(__int64 *m,__int64 *a,int n)	//x % m == a
{
	__int64 lcm = 1;
	for (int i = 1 ; i <= n ; i++)
		lcm = m[i] / GCD(m[i],lcm) * lcm;
	for (int i = 2 ; i <= n ; i++)
	{
		__int64 A = m[1] , B = m[i],d,x,y,c = a[i] - a[1];		//d 为 GCD(A,B) 
		d = exGCD(A,B,x,y);
		if (c % d != 0)		//无解 
			return -1;
		__int64 mod = m[i] / d;
		//然后套公式
		__int64 K = ((x * c / d) % mod + mod) % mod;
		a[1] = m[1] * K + a[1];
		m[1] = m[1] * m[i] / d;
	}
	if (a[1] == 0)		//如果最后合并的结果的余数为0，答案就是他们的最小公倍数 
		return lcm;
	return a[1];
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

变量