中国剩余定理学习笔记

中国剩余定理

有一组膜方程, 要求求出最小的\(x\) \[ \begin{cases}x = a_1(mod\ \ m_1) \\ x = a_2(mod \ \ m_2)\\ x = a_3(mod \ \ m_3)\\ .......... \\ x = a_n (mod \ \ m_n)\end{cases} \]

\(m_i\)两两互质时

我们引入中国剩余定理

定义\(M = \prod m_i\), 相当于要求我们构造出一个\(A = x (mod \ \ M)\)

定义\(M_i = \frac {M}{m_i}\), \(M_i^{-1}\)\(M_i\)在膜\(M\)意义下的逆元, 然后我们有下列等式: \[ a_i \cdot M_i \cdot M_i^{-1} = a_i(mod \ \ m_i)\\ a_i \cdot M_i \cdot M_i^{-1} = 0(mod \ \ M_i) \] 我们可以构造出一个最小解\(A = \sum a_i \cdot M_i \cdot M_i^{-1} (mod \ \ M)\)

\(PS\) : 这里求逆元必须要用\(Exgcd\), 因为不保证\(m_i\)为质数, 只保证\(M_i\)\(m_i\)互质

证明 : 不会, 待填坑......

代码 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stc++.h>

using namesapce std;

typedef long long LL;

const int maxn = 1e5 + 5;

LL n, m[maxn], a[maxn];

inline LL read(){
char ch = getchar(); LL u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline LL exgcd(LL a, LL b, LL &x, LL &y){
if(b == 0){x = 1; y = 0; return a;}
LL x0 = 0, y0 = 0;
LL d = exgcd(b, a % b, y0, x0);
x = x0; y = y0 - ((a / b) * x0);
return d;
}

inline LL china(LL *a, LL *m, LL n){
LL M = 1, ans = 0, tmp;
for(register int i = 1; i <= n; i++)M *= m[i];
for(register int i = 1; i <= n; i++){
int Mi = M / m[i], inv;
exgcd(Mi, m[i], inv, tmp);
ans = (ans + Mi * inv * a[i]) % M;
}
return (M + ans % M) % M;
}

int main(){
n = read();
for(register int i = 1; i <= n; i++)
a[i] = read(), m[i] = read();
cout << china(a, m, n);
return 0;
}

\(m_i\)为任意数

我们引入拓展中国剩余定理, 比如对于一组膜方程 : \[ \begin{cases} x = a_1 (mod \ \ m_1)\\ x = a_2(mod \ \ m_2)\end{cases} \] 我们将式子转换一下 \[ x = a_1 + m_1 \cdot y_1, x = a_2 + m_2 \cdot y_2 \]

\[ x = a_1 + m_1 \cdot y_1 = a_2 + m_2 \cdot y_2 \]

\[ a_1 - a_2 = m_2 \cdot y_2 - m_1 \cdot y_1 \]

然后我们设\(d = gcd(m_1, m_2)\), 并使得\(m_1 \cdot x + m_2 \cdot y = d\), 显然如果\(d \not\mid (a_1 - a_2)\)无解, 否则就是有解

然后使得\(y_1 = \frac {a_1 - a_2}{d} \cdot x, y_2 = \frac {a_1 - a_2}{d} \cdot y\) \[ A = a_1 + m_1 \cdot y_1 \] 我们就得到了一个合法解, \(x = A(mod \ \ lcm(m_1, m_2))\)

如果膜方程有很多的话, 就依次合并就好了

代码 :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int maxn = 1e5 + 5;

LL n, m[maxn], a[maxn];

inline LL read(){
char ch = getchar(); LL u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline LL exgcd(LL a, LL b, LL &x, LL &y){
if(b == 0){x = 1; y = 0; return a;}
LL x0 = 0, y0 = 0;
LL d = exgcd(b, a % b, y0, x0);
x = x0; y = y0 - ((a / b) * x0);
return d;
}

inline LL mul(LL x, LL y, LL mod){
x %= mod; y %= mod;
return (x * y - (LL)(((long double)x * y + 0.5) / mod) * mod) % mod;
}

inline LL exchina(LL *a, LL *m, LL n){
LL A = a[1], M = m[1], t, d, x, y;
for(register int i = 2; i <= n; i++){
d = exgcd(M, m[i], x, y);
if((a[i] - A) % d != 0)return -1;
t = m[i] / d;
x = mul(x, (a[i] - A) / d, t);
//x *= ((a[i] - A) / d);
//x = (t + x % t) % t;
A = (mul(M, x, M * t) + A) % (M * t); M *= t; A %= M;
}
return (A % M + M) % M;
}

int main(){
n = read();
for(register int i = 1; i <= n; i++)
m[i] = read(), a[i] = read();
cout << (exchina(a, m, n));
return 0;
}

例题讲解

1.BZOJ5418屠龙勇士

题目大意 : 给你一组以下形式的膜方程, 并让你求出最小解 \[ w_i \cdot x = a_i (mod \ \ p_i) \] 我们还是考虑转换一下式子 : \[ w_i \cdot x_i + p_i \cdot y_i = a_i \] 再考虑直接用\(Exgcd\)求出\(w_i \cdot a + p_i \cdot b = gcd(w_i, p_i) = d\), 显然如果\(d \not\mid a_i\)无解, 否则 \[ x = a + k \cdot \frac{p_i}{d} \] 这样我们将膜方程转化为了 : \[ \begin{cases} x = \frac{a_1}{gcd(w_1, p_1)} (mod \ \ \frac{p_1}{gcd(w_1, p_1)})\\ x = \frac{a_2}{gcd(w_2, p_2)} (mod \ \ \frac{p_2}{gcd(w_2, p_2)})\\ ..........\\ x = \frac{a_n}{gcd(w_n, p_n)} (mod \ \ \frac{p_n}{gcd(w_n, p_n)})\\ \end{cases} \] 这样我们就可以愉悦的套上\(ExCRT\)的模板了

但是上面我们所讨论的都是基于\(a_i \leq p_i\)的, 但是如果不保证这个条件的话就会出一些问题, 因为有可能我们根本就没有把血量杀到小于等于零但是在膜\(p_i\)的意义下血量就是零了, 所以这个不是完全正确的, 但是我们又发现所有不满足\(a_i \leq p_i\)的测试点都满足\(p_i = 1\), 所以对于这种情况答案就是 : \[ max\{\lceil \frac{a_i}{w_i} \rceil\} \] 最后关于选剑的问题我们直接用\(multiset\)维护一下就好了, 具体如下 :

先在\(multiset\)里面\(upper\_bound\)一下, 如果这个迭代器为\(begin()\)那么这个答案就是这个迭代器所代表的值, 否则就把这个迭代器减减一下, 就是答案了

Summary

水水水

咕咕咕