中国剩余定理 CRT

用户头像 发布于 4 天前 17 次阅读 OI

中国剩余定理 CRT

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

中国剩余定理（CRT）证明

定理陈述

对于一组互质的正整数 $m_1, m_2, \dots, m_k$，以及任意整数 $a_1, a_2, \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$ 下有唯一解。

证明步骤

构造解的存在性

  1. 定义总模数：
    $$M = m_1 m_2 \cdots m_k$$
    $$M_i = \frac{M}{m_i} \quad (i = 1, 2, \dots, k)$$
  2. 求逆元：
    由于 $m_i$ 两两互质，所以 $M_i$ 与 $m_i$ 互质：
    $$\gcd(M_i, m_i) = 1$$
    因此存在整数 $t_i$ 使得：
    $$M_i t_i \equiv 1 \pmod{m_i}$$
    这里的 $t_i$ 是 $M_i$ 在模 $m_i$ 下的乘法逆元。
  3. 构造解：
    令
    $$x = \sum_{i=1}^k a_i M_i t_i$$
  4. 验证解：
    对于任意 $j \in \{1, 2, \dots, k\}$：
  • 当 $i \neq j$ 时，$M_i$ 包含因子 $m_j$，所以 $M_i \equiv 0 \pmod{m_j}$
  • 当 $i = j$ 时，$M_j t_j \equiv 1 \pmod{m_j}$ 因此：
    $$x \equiv a_j \cdot 1 + \sum_{i \neq j} a_i \cdot 0 \equiv a_j \pmod{m_j}$$

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

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

那么对于每个 $i$：
$$x_1 \equiv x_2 \equiv a_i \pmod{m_i}$$
即：
$$m_i \mid (x_1 - x_2) \quad \forall i$$

由于 $m_i$ 两两互质，它们的乘积也整除 $x_1 - x_2$：
$$M \mid (x_1 - x_2)$$
所以：
$$x_1 \equiv x_2 \pmod{M}$$

代码：

#include<bits/stdc++.h>
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<=n;i++){
        cin>>a[i]>>b[i];
        m*=a[i];
    }
    for(int i=1;i<=n;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<<ans%m;
    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$$

解的存在条件

$$\gcd(a_1, a_2) \mid (b_2 - b_1)$$

令 $g = \gcd(a_1, a_2)$。

求解特解

用扩展欧几里得算法求：
$$a_1 X + a_2 Y = g$$

调整得：
$$k_1' = X \cdot \frac{b_2 - b_1}{g}$$

通解形式

$$k_1 = k_1' + \frac{a_2}{g} t \quad (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' \pmod{A'}$$

时间复杂度

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

代码

#include<bits/stdc++.h>
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(x<0){
		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<=n;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;
}