扩展CRT（扩展中国剩余定理）

给定 \(n\) 个同余模方程

\[\left\{\begin{aligned}

x\equiv\, & m_1(mod\quad a_1)\\

x\equiv\, & m_2(mod\quad a_2)\\

&\vdots\\

x\equiv\, & m_n(mod\quad a_n)

\end{aligned}

\right.

\]

不保证 \(gcd(m_i,m_j)=1(i\neq j)\) ,求最小的正整数解 \(x\)

2个方程的解

因为两两之间不互质，所以不能通过ex_gcd求解

尝试将问题缩小到两个方程，再逐步推出最后的解，有

\[\left

\{

\begin{aligned}

x\equiv\,&m_1(mod\quad a_1)\\

x\equiv\,&m_2(mod\quad a_2)

\end{aligned}

\right.

\]

也就等同于 \(\exists k_1,k_2\) ，使得

\[\left

\{

\begin{aligned}

x=&\,k_1a_1+m_1\\

x=&\,k_2a_2+m_2

\end{aligned}

\right.\tag{1}

\]

即有

\[k_1a_1+m_1=k_2a_2+m_2

\]

整理可得

\[k_1a_1-k_2a_2=m_2-m_1

\]

此时可用ex_gcd求解 \(k_1,k_2\) ，有解的充要条件是： \(gcd(a1,-a2)\mid(m_2-m_1)\)

记 \(d=gcd(a1,-a2)\),且 \(\exists k_1^{'},k_2^{'}\) ,使得

\[k_1^{'}a_1-k_2^{'}a_2=d

\]

可以通过ex_gcd求解得出 \(k_1^{'},k_1^{'}\)的特解，设 \(t=\frac{m_2-m_1}{d}\),则

\[\left

\{

\begin{aligned}

k_1&=k_1^{'}t\\

k_2&=k_2^{'}t\\

\end{aligned}

\right.

\]

通解形式为（ \(k\) 为任意整数）

\[\left

\{

\begin{aligned}

k_1&=k_1^{'}t+k\frac{-a_2}{d}\\&=k_1+k\frac{-a_2}{d}\\

k_2&=k_2^{'}t-k\frac{a_1}{d}\\&=k_2-k\frac{a_1}{d}\\

\end{aligned}

\right.

\]

再把 \(k_1\) 的通解带入到 \(x=k_1a_1+m_1\) 中

\[\begin{aligned}

x&=(k_1+k\frac{-a_2}{d})a_1+m_1\\

&=k_1a_1+k\frac{a_1(-a_2)}{d}+m_1\\

&=k\frac{a_1(-a_2)}{d}+k_1a_1+m_1\\

&=\underbrace{k}_{k_1}\underbrace{lcm(a_1,-a_2)}_{a_1}+\underbrace{k_1a_1+m_1}_{m_1}

\end{aligned}

\]

这样就得到了新的

\[\left

\{

\begin{aligned}

k_1&=k\quad\\

a_1&=lcm(a_1,-a_2)\\

m_1&=k_1a_1+m_1\\

\end{aligned}

\right.

\]

与一开始方程组 \((1)\) 中的表达形式相同，这样就将两个方程合并成了一个方程

\[x=k_1a_1+m_1\tag{2}

\]

此时 \(x\) 的解就是 \(m_1\) 在模 \(a_1\) 下的最小正整数解

n个方程的解

经过 \(n-1\) 轮整合，可以把 \(n\) 个方程合并成为一个方程

\[x=ka+m

\]

最终的结果就是

\[x=(m\%a+a)\%a

\]

例题

204. 表达整数的奇怪方式

• 每一轮合并得出的方程 \((2)\) 的 \(k_1\) 都保证是最小正整数解，这样得到新的 \(m_1\) 是最小正整数解，以防在计算过程中溢出


• 保证最后的最小正解，模数也应当为正

#include
#include
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) {
x=1;
y=0;
return a;
}
ll d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
int main() {
int n;
scanf("%d",&n);
ll a1,m1;
scanf("%lld%lld",&a1,&m1);
bool flag=true;
for(int i=0;i ll a2,m2;
scanf("%lld%lld",&a2,&m2);
a2=-a2;
ll k1,k2;
ll d=exgcd(a1,a2,k1,k2);
if((m2-m1)%d) {
flag=false;
break;
}
k1=k1*((m2-m1)/d);//特解
ll temp=abs(a2/d);
k1=(k1%temp+temp)%temp;//通解中保证最小正整数解
m1=k1*a1+m1;
a1=a1/d*a2;
}
if(flag) {
if(a1<0) a1=-a1;
m1=(m1%a1+a1)%a1;//保证最后的最小正解，模数也应当为正
printf("%lld",m1);
} else puts("-1");
return 0;
}


参考

• 算法讲堂[基础]-数论基础定理与算法


• https://www.acwing.com/activity/content/code/content/53307/