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;
}