中国剩余定理 CRT

中国剩余定理 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 下有唯一解。 证明步骤 构造解的存在性 定义总模数： M = m_1 m_2 \cdots m_k M_i = \frac{M}{m_i} \quad (i = 1, 2, \dots, k) 求逆元： 由于 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 下的乘法逆元。 构造解： 令 x = \sum_{i=1}^k a_i M_i t_i 验证解： 对于任意 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 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 解的存在条件 \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 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; }`