# 扩展中国剩余定理 exCRT 学习笔记

• gcd/lcm
• exgcd
• 快速乘

## 用途

$$\left\{ \begin{matrix} x\equiv a_1\pmod{b_1}\\ x\equiv a_2\pmod{b_2}\\ \cdots\\ x\equiv a_n\pmod{b_n} \end{matrix}\right.$$

## 解法推导

\left\{ \begin{aligned} &x\equiv a_{i-1}&\pmod{b_{i-1}}\\ &x\equiv a_i&\pmod{b_i} \end{aligned}\right.

\left\{ \begin{aligned} &x+k_1b_i=a_i\\ &x+k_2b_{i-1}=a_{i-1} \end{aligned}\right.

$$k_1b_i-k_2b_{i-1}=a_i-a_{i-1}$$

$$k_1’b_i+k_2’b_{i-1}=\gcd(b_i,b_{i-1})$$

$$\frac {k_1}{k_1′}=\frac{k_2}{k_2′}=\frac{a_i-a_{i-1}}{\gcd(b_i,b_{i-1})}$$

$$k_{1_0}=k_0\times \frac{a_i-a_{i-1}}{\gcd(b_i,b_{i-1})}$$

$$k_{1_0}+t\times \frac{b_{i-1}}{\gcd(b_i,b_{i-1})},\ t\in \mathbb Z$$

### 不定方程的通解

$$\left\{ \begin{matrix} x=x_0\\ y=y_0 \end{matrix} \right.$$

$$x+k_1b_i=a_i$$

$$x+\left(k_{1_0}+t\times \frac{b_{i-1}}{\gcd(b_i,b_{i-1})}\right)\times b_i=a_i,\ t\in \mathbb Z$$

$$x+b_ik_{1_0}+t\times \frac{b_ib_{i-1}}{\gcd(b_i,b_{i-1})}=a_i,\ t\in \mathbb Z\\ t\times\operatorname{lcm}(b_i,b_{i-1})=a_i-x-b_ik_{1_0},\ t\in \mathbb Z$$

$$a_i-x-b_ik_{1_0}|\operatorname{lcm}(b_i,b_{i-1})\\ a_i-x-b_ik_{1_0}\equiv 0\pmod{\operatorname{lcm}(b_i,b_{i-1})}\\ x\equiv a_i-b_ik_{1_0}\pmod{\operatorname{lcm}(b_i,b_{i-1})}$$
$\equiv$ 符号右边的都是已知量，这时我们就把两个方程结合到一块了。

$$x\equiv a_n\pmod{\operatorname{lcm}(b_1,b_2,\cdots,b_m)}$$
（$a_n$ 是合并 $n-1$ 个式子后的新 $a_n$，上述过程中每一步都会更新 $a_i$）

（上下两部分实质相同）

## 解法简述

\left\{ \begin{aligned} &x\equiv a_{i-1}&\pmod{b_{i-1}}\\ &x\equiv a_i&\pmod{b_i} \end{aligned}\right.

\left\{ \begin{aligned} &x+k_1b_i=a_i\\ &x+k_2b_{i-1}=a_{i-1} \end{aligned}\right.

$$k_1’b_i-k_2’b_{i-1}=\gcd(b_i,b_{i-1})$$

$$k_1b_i-k_2b_{i-1}=a_i-a_{i-1}$$

$$k_{1_0}=k_1’\times \frac{a_i-a_{i-1}}{\gcd(b_i,b_{i-1})}$$

$$k_1=k_{1_0}+t\times\frac{b_{i-1}}{\gcd(b_i,b_{i-1})}$$

$$x+k_{1_0}b_i+t\times \operatorname{lcm}(b_i,b_{i-1})=a_i$$

$$x\equiv a_i-k_{1_0}b_i\pmod{\operatorname{lcm}(b_i,b_{i-1})}$$

## 代码

#include<cstdio>
#define ll long long
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(!b)
{
x=1,y=0;
return a;
}
ll g=exgcd(b,a%b,y,x);
y-=a/b*x;
return g;
}
ll qmul(ll x,ll y,ll p)
{
ll ans=0,f=1;
if(x<0)
{
x=-x;
f=-f;
}
if(y<0)
{
y=-y;
f=-f;
}
while(y)
{
if(y&1)
ans=(ans+x)%p;
x=(x+x)%p;
y>>=1;
}
return ans*f;
}
ll a[100100],b[100100];
int main()
{
int n;
ll x,y;
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lld%lld",&b[i],&a[i]);
for(int i=2;i<=n;++i)
{
ll g=exgcd(b[i],b[i-1],x,y);
ll t=b[i-1]/g;//k1 的最小波动 Δ
x=qmul(x,(a[i]-a[i-1])/g,t);
x=(x%t+t)%t;
a[i]-=qmul(x,b[i],b[i]/g*b[i-1]);
b[i]=b[i]/g*b[i-1];
a[i]=(a[i]%b[i]+b[i])%b[i];
}
printf("%lld\n",(a[n]%b[n]+b[n])%b[n]);
return 0;
}


### 3 说点什么

3 Comment threads
0 Thread replies
0 Followers

Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
Subscribe

[…] exCRT […]

[…] 【exCRT学习笔记】 […]

… [Trackback]

[…] Read More Info here on that Topic: wjyyy.top/3375.html […]

/* */