前置知识

中国剩余定理(CRT)

目的

求最小的正整数 $x$ ，使其满足

${\begin{matrix} <mstyle displaystyle="false" scriptlevel="0"> x \equiv a_{1} (m o d <mtext> </mtext> m) </mstyle> \\ <mstyle displaystyle="false" scriptlevel="0"> x \equiv a_{2} (m o d <mtext> </mtext> m_{2}) </mstyle> \\ <mstyle displaystyle="false" scriptlevel="0"> ⋮ </mstyle> \\ <mstyle displaystyle="false" scriptlevel="0"> x \equiv a_{n} (m o d <mtext> </mtext> m_{n}) </mstyle> \end{matrix}$

其中 $m_{1}, m_{2} \dots m_{n}$ 互质

求法

令 $\begin{matrix} <mstyle displaystyle="true" scriptlevel="0"> M = <munderover> \prod i = 1 n </munderover> m_{i} </mstyle> \end{matrix}$

设 $ω_{i} = \frac{M}{m_{i}}$

$ω_{i}^{- 1}$ 为 $ω_{i}$ 在 $m o d <mtext> </mtext> M$ 下的逆元

则有
$\begin{matrix} <mstyle displaystyle="true" scriptlevel="0"> x = <munderover> \sum i = 1 n </munderover> a_{i} ω_{i} ω_{i}^{- 1} m o d <mtext> </mtext> M </mstyle> \end{matrix}$

当对 $m_{i}$ 取模时，除了有 $ω_{i}$ 的项，其余项都是 $m_{i}$ 的倍数，也就是说它们 $m o d <mtext> </mtext> m_{i}$ 是为 $0$ 的，最后得到的结果就是 $a_{i}$

$m_{1}, m_{2} \dots m_{n}$ 互质
为了保证是最小正整数解，我们乘以 $ω_{i}$ 的逆元，这样保证了其不会过大

Code

#define ll long long
#define ull unsigned long long

void ex_gcd (ll a,ll b,ll &x,ll &y)
{
	if (!b){	x=1,y=0;return;}
	ex_gcd(b,a%b,x,y);
	int tmp=x;
	x=y,y=tmp-a/b*y;
}

ll mul (ll x,ll y,const ll mod)//快速乘
{
	x%=mod,y%=mod;
	ll z=(long double)x*y/mod;
	ll ans=(ull)x*y-(ull)z*mod;
	return (ans+mod)%mod;
}

ll crt (int *a,int *m,int n)
{
	ll M=1,ans=0;
	for (int i=1;i<=n;++i)	M*=m[i];
	for (int i=1;i<=n;++i){
		ll ni,jk;
		ex_gcd(M/m[i],m[i],ni,jk);//ni 逆元
		ans=(ans+mul(mul(M/m[i],a[i],M),ni,M))%M;
	}
	return ans;
}

扩展中国剩余定理(EXCRT)

目的

求最小的正整数 $x$ ，使其满足

其中 $m_{1}, m_{2} \dots m_{n}$ 不一定互质

解法

对于 $C R T$ 而言，这里的条件变为 $m$ 之间可以不互质了
显然是不能向原来那样直接求了
考虑已经知道了前 $i - 1$ 个方程的答案 $x$
设前 $i - 1$ 个 $m$ 的最小公倍数 $l c m (m 1, m 2 \dots m_{i - 1}) = M$
现在考虑第 $i$ 个方程
$x \equiv a_{i} (m o d <mtext> </mtext> m_{i})$
我们知道前 $i - 1$ 个方程的最小解为 $x$ ，那么其通用解就是 $x + k M$
因为 $k M$ 对前 $i - 1$ 个 $m$ 取模肯定是等于 $0$ 的
那么考虑了第 $i$ 个方程后的解应也是如上的一个形式
就设为 $x + k M$ 吧
那么我们就是要求关于 $k$ 的这样的方程
$k M + x \equiv a_{i} (m o d <mtext> </mtext> m_{i})$
其中 $x, a_{i}, m_{i}$ 都是已知的
这就是一个简单的同余方程了
$k M - p m_{i} = a_{i} - x$
其中两个未知数 $k, p$
用 $e x_{g} c d$ 求解即可
无解条件就是上述方程无解

code

#define ll long long
#define ull unsigned long long

ll ex_gcd (ll a,ll b,ll &x,ll &y)
{
	if (!b){	x=1,y=0;return a;}
	ll g=ex_gcd(b,a%b,x,y);
	int tmp=x;
	x=y,y=tmp-a/b*y;
	return g;
}

ll mul (ll a,ll b,ll mod)//快速乘
{
	a%=mod,b%=mod;
	ll c=(long double)a*b/mod;
	ll ans=(ull)a*b-(ull)c*mod;
	return (ans+mod)%mod;
}

ll ex_crt (ll *a,ll *m,int n)
{
	ll ans=a[1]%m[1],M=m[1];
	for (int i=2;i<=n;++i){
		ll gcd,x,y,c=(a[i]%m[i]-ans%m[i]+m[i])%m[i];
		gcd=ex_gcd(M,m[i],x,y);
		if (c%gcd)	return -1;
		x=mul(x,c/gcd,m[i]/gcd);
		ll lm=M;
		M=M/gcd*m[i];
		ans=((ans+mul(x,lm,M)%M)%M+M)%M;
	}
	return ans;
}

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧

中国剩余定理和扩展中国剩余定理

文章目录

前置知识

中国剩余定理(CRT)

目的

求法

Code

扩展中国剩余定理(EXCRT)

目的

解法

code