中国剩余定理

中国剩余定理

中国剩余定理

中国剩余定理

中国剩余定理，CRT是用来求多组同余方程的解，前提是模数$m_i$两两互质 $$f(x)=\{\begin{array}{r}x\equiv a_1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_1)\\ x\equiv a_2(\mathrm{m}\mathrm{o}\mathrm{d}{m}_2)\\ x\equiv a_3(\mathrm{m}\mathrm{o}\mathrm{d}{m}_3)\\ ...\\ x\equiv a_k(\mathrm{m}\mathrm{o}\mathrm{d}{m}_k)\end{array}$$

设$M=[m_1,m_2,m_3,...,m_k]={\prod }_{i=1}^k{m}_i$ , $m{k}_i=\frac{M}{m_i}$ 且$t_i$是同余方程$m{k}_i\ast t_i\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)$的最小非负整数解

一、

因为对于任意 $j$$̸=$ $i$ , $m{k}_i\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{m}_j)$

所以 $m{k}_i\ast a_i\ast t_i\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{m}_j)$

又因为 $m{k}_i\ast t_i\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)$

所以 $m{k}_i\ast t_i\ast a_i\equiv a_i(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)$

二、

所以对于任意 $j$$̸=$ $i$ , $m{k}_j\ast a_j\ast t_j\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)$

所以$m{k}_j\ast a_j\ast t_j+m{k}_i\ast t_i\ast a_i\equiv a_i(\mathrm{m}\mathrm{o}\mathrm{d}{m}_i)$

把所有 $j$$̸=$ $i$ 的式子求和，再与$m{k}_i\ast t_i\ast a_i$ 求和，

得到${\sum }_{i=1}^{k}m{k}_i\ast t_i\ast a_i=x$的一组特解

通解为 $x+i\ast M(i\in Z)$

扩展中国剩余定理

模数$m_i$为不一定两两互质的整数 求x的最小非负整数解

假设已经求出前k-1个方程组成的同余方程组的一个解为x 且有$M={\prod }_{i-1}^{k-1}{m}_i$ 则前k-1个方程的方程组通解为$x+i\ast M(i\in Z)$

那么对于加入第$k$个方程后的方程组 我们就是要求一个正整数$t$，使得 $x+t\ast M\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}{m}_k)$

转化一下上述式子得 $t\ast M\equiv a_k-x(\mathrm{m}\mathrm{o}\mathrm{d}{m}_k)$ $M\ast t+m_k\ast p=a_k-x$ ——①

设$g=(M,m_k)$ 解$M\ast t+m_k\ast p=g$，得到答案$t_0$ 要模b/gcd是因为要求出通解中的最小解

对于这个式子我们已经可以通过扩展欧几里得求解$t$ 若该同余式无解，则整个方程组无解 若有，则前k个同余式组成的方程组的一个解，解为$x_k=x+t\ast M$

所以整个算法的思路就是求解k次扩展欧几里得

#include <bits/stdc++.h> #define ll long long #define MAX 100005 using namespace std; ll n, m, ans; ll a[MAX], b[MAX]; ll exgcd(ll a, ll b, ll &x, ll &y){ if(!b){ x = 1, y = 0; return a; } ll res = exgcd(b, a%b, x, y); ll t = x; x = y, y = t-a/b*y; return res; } ll mul(ll a, ll b, ll mod){ ll res = 0, base = a; while(b){ if(b&1){ res = (res+base)%mod; } base = (base+base)%mod; b >>= 1; } return res; } ll excrt(){ m = b[1], ans = a[1]; for(int i = 2; i <= n; i++){ ll p = ((a[i]-ans)%b[i]+b[i])%b[i]; ll x, y; //mx=p (mod b[i]) ll gcd = exgcd(m, b[i], x, y); if(p % gcd) return -1; x = mul(x, p/gcd, b[i]/gcd); ans += x*m; m *= b[i]/gcd; ans = (ans%m+m)%m; } return (ans%m+m)%m; } int main() { cin >> n; for(int i = 1; i <= n; i++){ scanf("%lld%lld", &b[i], &a[i]); } printf("%lld\n", excrt()); return 0; }

$t\ast M\equiv a_k-x(\mathrm{m}\mathrm{o}\mathrm{d}{m}_k)$

$d=(M,m_k)$

$t\ast M\equiv d(\mathrm{m}\mathrm{o}\mathrm{d}{m}_k)$