中国剩余定理 CRT

P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

中国剩余定理（CRT）证明

定理陈述

对于一组互质的正整数 $m_1,m_2,\text{[PARSE ERROR: Undefined("Command("dots")")]},m_k$，以及任意整数 $a_1,a_2,\text{[PARSE ERROR: Undefined("Command("dots")")]},a_k$，同余方程组：

\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases}

在模 $M=m_1{m}_2\cdots m_k$ 下有唯一解。

证明步骤

构造解的存在性

• 定义总模数： $$M=m_1{m}_2\cdots m_k$$ $$M_i=\frac{M}{m_i}(i=1,2,\text{[PARSE ERROR: Undefined("Command("dots")")]},k)$$

• 求逆元： 由于 $m_i$ 两两互质，所以 $M_i$ 与 $m_i$ 互质： $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(M_i,m_i)=1$$ 因此存在整数 $t_i$ 使得： $$M_i{t}_i\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}{m}_i$$ 这里的 $t_i$ 是 $M_i$ 在模 $m_i$ 下的乘法逆元。

• 构造解： 令 $$x=\sum _{i=1}^k{a}_i{M}_i{t}_i$$

• 验证解： 对于任意 $j\in \{1,2,\text{[PARSE ERROR: Undefined("Command("dots")")]},k\}$：

• 当 $i\ne j$ 时，$M_i$ 包含因子 $m_j$，所以 $M_i\equiv 0\text{[PARSE ERROR: Undefined("Command("pmod")")]}{m}_j$

• 当 $i=j$ 时，$M_j{t}_j\equiv 1\text{[PARSE ERROR: Undefined("Command("pmod")")]}{m}_j$ 因此： $$x\equiv a_j·1+\sum _{i\ne j}{a}_i·0\equiv a_j\text{[PARSE ERROR: Undefined("Command("pmod")")]}{m}_j$$

证明解的唯一性（在模 $M$ 下）

假设存在两个解 $x_1$ 和 $x_2$，都满足同余方程组。

那么对于每个 $i$： $$x_1\equiv x_2\equiv a_i\text{[PARSE ERROR: Undefined("Command("pmod")")]}{m}_i$$ 即： $$m_i\mid (x_1-x_2)\forall i$$

由于 $m_i$ 两两互质，它们的乘积也整除 $x_1-x_2$： $$M\mid (x_1-x_2)$$ 所以： $$x_1\equiv x_2\text{[PARSE ERROR: Undefined("Command("pmod")")]}M$$

代码：

#include
using namespace std;
#define int long long
const int N=12;
int n,m=1,x,y,ans;
int a[N],b[N];

int qmul(int a,int b,int mod){
    int res=0;
    a%=mod;
    while(b){
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}

void exgcd(int A,int B,int &x,int &y){
    if(B==0){x=1;y=0;return;}
    exgcd(B,A%B,y,x);
    y-=A/B*x;
}

signed main(){
    cin>>n;
    for(int i=1;i>a[i]>>b[i];
        m*=a[i];
    }
    for(int i=1;i

`#include
using namespace std;
#define int long long
const int N=12;
int n,m=1,x,y,ans;
int a[N],b[N];

int qmul(int a,int b,int mod){
    int res=0;
    a%=mod;
    while(b){
        if(b&1) res=(res+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return res;
}

void exgcd(int A,int B,int &x,int &y){
    if(B==0){x=1;y=0;return;}
    exgcd(B,A%B,y,x);
    y-=A/B*x;
}

signed main(){
    cin>>n;
    for(int i=1;i
        cin>>a[i]>>b[i];
        m*=a[i];
    }
    for(int i=1;i
        int c=m/a[i];
        exgcd(c,a[i],x,y);
        x=(x%a[i]+a[i])%a[i];
        int t=qmul(b[i],c,m);
        t=qmul(t,x,m);
        ans=(ans+t)%m;
    }
    cout
    return 0;
}`

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

问题描述

求解模数不一定互质的同余方程组： \begin{cases} x \equiv b_1 \pmod{a_1} \\ x \equiv b_2 \pmod{a_2} \\ \vdots \\ x \equiv b_n \pmod{a_n} \end{cases}

核心思想：合并两个方程

方程等价形式

\begin{cases} x = a_1 k_1 + b_1 \\ x = a_2 k_2 + b_2 \end{cases}

联立方程

$$a_1{k}_1-a_2{k}_2=b_2-b_1$$

解的存在条件

$$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a_1,a_2)\mid (b_2-b_1)$$

令 $g=\text{[PARSE ERROR: Undefined("Command("gcd")")]}(a_1,a_2)$。

求解特解

用扩展欧几里得算法求： $$a_{1}X+a_{2}Y=g$$

调整得： $$k_{1^{\prime }}=X·\frac{b_2-b_1}{g}$$

通解形式

$$k_1=k_{1^{\prime }}+\frac{a_2}{g}t(t\in \mathbb{Z})$$

代回求 $x$

\begin{aligned} x &= a_1 k_1 + b_1 \\ &= a_1 \left(k_1' + \frac{a_2}{g} t\right) + b_1 \\ &= \frac{a_1 a_2}{g} t + \left(a_1 k_1' + b_1\right) \end{aligned}

合并结果

令： \begin{aligned} A' &= \mathrm{lcm}(a_1, a_2) = \frac{a_1 a_2}{g} \\ B' &= a_1 k_1' + b_1 \end{aligned}

则： $$x\equiv B^{\prime }\text{[PARSE ERROR: Undefined("Command("pmod")")]}{A}^{\prime }$$

时间复杂度

每次合并需要一次扩展欧几里得算法，时间复杂度 $O\left(\log \min \right(A,a_i\left)\right)$。 总时间复杂度 $O\left(n\log M\right)$，其中 $M=\max \left(a_i\right)$。

代码

#include
using namespace std;
#define int __int128

int n;
int a1,a2,b1,b2,x,y;

inline __int128 read(){
	__int128 x=0,f=1;
	char ch=getchar();
	while(ch'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch9) write(x/10);
	putchar(x%10+'0');
}

void exgcd(int A,int B,int &x,int &y){
	if(B==0){x=1;y=0;return;}
	exgcd(B,A%B,y,x);
	y-=A/B*x;
}

signed main(){
	n=read(),a1=read(),b1=read();
	for(int i=2;i

`#include
using namespace std;
#define int __int128

int n;
int a1,a2,b1,b2,x,y;

inline __int128 read(){
	__int128 x=0,f=1;
	char ch=getchar();
	while(ch'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch'9') x=x*10+ch-'0',ch=getchar();
	return x*f;
}

inline void write(__int128 x){
	if(x0){
		putchar('-');
		x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

void exgcd(int A,int B,int &x,int &y){
	if(B==0){x=1;y=0;return;}
	exgcd(B,A%B,y,x);
	y-=A/B*x;
}

signed main(){
	n=read(),a1=read(),b1=read();
	for(int i=2;i
		a2=read(),b2=read();
		int g=__gcd(a1,a2);
		exgcd(a1,a2,x,y);
		x*=(b2-b1)/g;
		x=(x%(a2/g)+(a2/g))%(a2/g);
		int A1=a1,B1=b1;
		a1=A1*a2/__gcd(A1,a2);
		b1=A1*x+B1;
	}
	write((b1%a1+a1)%a1);
	return 0;
}`