Chinese Remainder Theorem

$x≡ai(mod mi)$
中国剩余定理CRT

1.定义

Th.
给出一元线性同余线性方程组
$x ≡ a1 \bmod m1$
$x ≡ a2 \bmod m2$
...
$x ≡ an \bmod mn$
定理指出假设素数$m1,m2...mn$两两互素,对任意的整数$a1,a2...an$
上述方程有解，并且可以通过如下步骤构造通解：
1>计算$M=\prod_{i = 1}^{n}mi,Mi = \dfrac{M}{mi}$(即,Mi是除$mi$之外的其他整数的乘积)
2>计算$ti$为$Mi$模$mi$的逆,对于$i=1,2,..,n,$计算满足$tiMi≡1(\bmod mi)$的$ti$
3>上述方程的通解为:
$x=a1t1M1+a2t2M2+...+antnMn+kM,k∈Z$
在模$M$的意义下,方程组只有一个解$x=a1t1M1+a2t2M2+...+antnMn$

2.写法

1.互质的写法(useless)

$eg.$
$x \bmod 3 = 2$
$x \bmod 5 = 3$
$x \bmod 7 = 4$

$x1 \bmod 3 = 1$
$x1 \bmod 5 = 0 ————>x1=70$
$x1 \bmod 7 = 0$

$x2 \bmod 3 = 0$
$x2 \bmod 5 = 1 ————>x2=21$
$x2 \bmod 7 = 0$

$x3 \bmod 3 = 0$
$x3 \bmod 5 = 0 ————>x3=15$
$x3 \bmod 7 = 1$

$x = 2*70+3*21+4*15 = 263$
2(1,0,0) 3(0,1,0) 4*(0,0,1)
(2,0,0) (0,3,0) (0,0,4)
(2,3,4）
$x$%$105 = 53$

总结:
对于$n$个
$x \bmod mi = ai$

我们先去解$n$个
$xi \bmod mi = 1$
$xi \bmod mj = 0(其他i≠j) $

$xi \bmod (m1*m2..mi-1*mi+1...mn) = 0$
即 $xi \bmod (\frac{M}{mi}) = 0$
$ xi \bmod mi = 1$ 设$xi = (\frac{M}{mi})t$ 则有$(\frac{M}{mi})t \bmod mi = 1$

比如上述例子$ 3 5 7$
$35t1 ≡ 1(\bmod 3)$
$t1 = 2$
$∴x1 = 70$

$21t2 ≡ 1(\bmod 5)$
$t2 = 1$
$x2 = 21$

$15t3 ≡ 1(\bmod 7)$
$t3 =1$
$x3 = 15$

即$Mi*ti ≡ 1(\bmod mi)$
$xi = Miti$
$ x = Σai*xi$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e5 + 7;
int n, a[N], m[N];
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if(b == 0){
        x = 1; y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, x, y);
    ll z = x;x = y;y = z - (a / b) * x;
    return d;
}
int main()
{
   int t;
   cin>>t;
   while(t--)
   {
	   	ll M = 1;
	    scanf("%d", &n);
	    for(int i = 1; i <= n; ++ i) 
	    {
	        scanf("%d%d", &a[i], &m[i]);
	        M *= m[i];
	    }
	    ll res = 0;
	    for(int i = 1; i <= n; ++ i) 
	    {
	        ll Mi = M / m[i];
	        ll ti, y;
	        //exgcd求逆元：解同余方程：ax + my = 1;(ax ≡ 1 mod m)
	        ll d = exgcd(Mi, m[i], ti, y);
	        ti = (ti % m[i] + m[i]) % m[i];
	        res += a[i] * ti * Mi;
	    }
	    printf("%lld\n", (res % M + M) % M);//可能为负数，所以需要处理一下
   }
    return 0;
}

2.对于不互质的情况(增量法)

一开始有两个方程$x≡a(\bmod b),x ≡ c(\bmod d)$
设$x = bt+a;$
那么有$bt+a≡c(\bmod d),$
$bt ≡ c-a(\bmod d)$
要有解$,c-a$要被$g=\gcd(b,d)$整除
$b't≡(c-a)'(\bmod \dfrac{d}{(b,d)})$
$t ≡ (c-a)'*(b'^-1)(mod \dfrac{d}{(b,d)})$
设$t0 = (c-a)'*(b'^{-1})$
转化为线性同余方程，
然后解出$t ≡ t0(\bmod \dfrac{d}{(d,b)})$
$ t ≡ t0(\bmod \dfrac{d}{g})$ 再t代回去,$x ≡ bt0+a(\bmod \dfrac{bd}{g})$ 得出$x ≡ x0(\bmod[b,d])$ 然后下一条方程, 可以解决模数不互质的情况即在不互质的情况下，要么无解，要么在$\bmod([b,d])$的意义下有唯一解

$eg$.
$x ≡ 2(mod 3)①$
$x ≡ 3(mod 5)②$
$x ≡ 4(mod 7)③$

先连立前两个方程$x ≡ 8(\bmod 15)④$
在联立$③④得x≡53(\bmod 105)$

$eg2.$

$x ≡ 3(\bmod 4)①$
$x ≡ 5(\bmod 6)②$
$x ≡ 5(mod 9)③$

$x = 4t+3$代入$②得：4t+3 ≡ 5(\bmod 6)$
$4t ≡ 2(\bmod 6)$
$ 2t ≡ 1(\bmod 3) t ≡ 2(\bmod 3)$ 再将$t$带回去$x ≡ 11(\bmod 12)④$ 在联立③④：令$x = 12t+11$代入③得:$12t+11≡5(\bmod 9)$
$12t ≡ 3(\bmod 9)$
$4t ≡ 1(\bmod 3)$
$t ≡ 1(\bmod 3)$
再将$t$带回去$x ≡ 23(\bmod 36)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x = 1,y = 0;
		return a;
	}
	ll d = exgcd(b,a%b,y,x);
	y -= (a/b)*x;
	return d;
}

void merge(ll &a,ll&b,ll c,ll d)
{
	if(a==-1&&b==-1)return;
	//bt = c-a(mod d)
	ll x,y;
	ll g = exgcd(b,d,x,y);
	//x = b^(-1)
	if((c-a)%g!=0)
	{
		a = b = -1;
		return;
	}
	d/=g;//d'
	ll t0 = ((c-a)/g)%d*x%d;
	if(t0<0)t0+=d;
	a = b*t0+a;
	b = b*d;
}

void solve()
{
	cin>>n;
	ll a = 0,b = 1;//x ≡ a(mod b)
	for(int i = 1;i<=n;i++)
	{
		int c,d;
		cin>>c>>d;
		merge(a,b,c,d);
	}
	cout<<a<<endl;
}


int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

例题：中国剩余定理2

一共$T$组数据，每组数据，给定$n$个方程，
$x≡ai(\bmod mi)$。判断方程是不是有解。

x mod 合数 = a ==>等价于模数是素数幂的方程，再去判断有没有解，我们还是用中国剩余定理
$eg.x \bmod 10 = 1 <==> x \bmod 2 = 1(*)且x \bmod 5 = 1$

$eg.x \bmod 12 = 3 <==> x \bmod 4 = 3(*)且x \bmod 3 = 0$

模数按照素数的幂次分类，比如(*)式看成一类，我们只需要看其中指数最高的那个方程，但我们还是要判前面满不满足的，比如我们既有一个方程$x \mod 4 = 3$又有个方程$x \mod 4 = 2$这样也是不行的

转化：
对合数取模
|
CRT
↓
对素数幂取模

即：

$x \bmod mi = ai$
|
CRT
↓
$x \bmod p^{ei} = ?$ 然后对于每个素数幂的我们都check一下是否都是满足的
|
CRT
↓

若满足，则有解

总结：对合数取模 <=CRT 是桥梁=> 对素数幂取模

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool solve()
{
	int n;
	cin>>n;
	map<int,vector<pair<int,int>>>eqns;

	for(int i = 1;i<=n;i++)
	{
		int a,m;
		cin>>a>>m;
		for(int j = 2;j*j<=m;j++)//分解为素数幂
		{
			if(m%j==0)
			{
				int p = j,pe = 1;
				while(m%j==0)
					m/=j,pe*=j;
				eqns[p].push_back({pe,a%pe});	
			}
		}
		if(m>1)eqns[m].push_back({m,a%m});
	}
	for(auto eq:eqns)
	{
		auto eqn = eq.second;
		int v = max_element(eqn.begin(),eqn.end())->second;//最后的余数由指数最大的所决定
		for(auto p:eqn)
		{
			if(v%p.first!=p.second)return false;
		}
	}
	return true;
}


int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		if(solve())
			cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}