裴蜀定理
$a\cdot x +b\cdot y=c,x,y\in N_+$成立的充要条件是$\gcd(a,b)|c$
该定理可推广至多个未知数方程。
GCD
GCD就是最大公约数，最大公约数和最小公约数的求法都非常简单，这里直接给出求法。
最大公约数：通常采用辗转相除法，也可以使用更相减损术。我们主要用辗转相除法（欧几里得算法）。
gcd具有一些性质：
- $\gcd(a,b)=\gcd(-a,b)$
- $\gcd(a,b)=\gcd(b,a\bmod b)$，这个性质应用于辗转相除法
- $\gcd(a,b)=\gcd(b, a -b)$，这个性质应用于更相减损术
1 | ll GCD(ll a, ll b) { |
exGCD
扩展欧几里得定律，用于求解形如$a\cdot x+b\cdot y=\gcd(a, b)$的不定方程。
下面我们来简单说明一下其原理：
由性质2可知$\gcd(a,b)=\gcd(b,a\bmod b)$
我们设$\gcd(b,a\bmod b)=b\cdot x’+(a\bmod b)\cdot y’$
则有$a\cdot x+b\cdot y=b\cdot x’+(a\bmod b)\cdot y’$
我们知道，$a\bmod b=a-b\cdot\lfloor \dfrac{a}{b}\rfloor$
由此得$a\cdot x + b\cdot y=a\cdot y’+b\cdot(x’-\lfloor\dfrac{a}{b}\rfloor\cdot y’)$
因此我们可以知道，$x,y$的一组可行解为$(x,y)=(y’,x’-\lfloor\dfrac{a}{b}\rfloor\cdot y’)$
那么其边界条件是什么呢？我们知道，欧几里得算法执行到最后$a’\bmod b’=0$，即$a’$一定是$b’$的整数倍，所以在我们递归下一次时，$y’$的系数实际上变成了0，而$x’$的系数为$b’$，且$b’=\gcd(a,b)$，因此边界条件为$x=1,y=0$。
于是我们的解法就出来了，递归地实现欧几里得算法，当求到边界时设$x=1,y=0$，然后在回溯的过程中根据上述推导的公式一步步求解。
1 | //这里要采用递归写法，因为要回溯 |
显然，这里我们求出了一组可行解，很容易得出该不定方程的通解为$x’=x_0+\dfrac{k\cdot b}{\gcd(a,b)},y’=y_0-\dfrac{k\cdot a}{\gcd(a,b)}$。
得到这个结果后，我们可以推导出一般的二元一次不定方程解法。
对于$a\cdot x+b\cdot y=c$，若$\gcd(a,b)\not|c$则无解，否则我们将$a\cdot x_0+b\cdot y_0=\gcd(a,b)$变形为
由此可知$x_1=\dfrac{c\cdot x_0}{\gcd(a,b)},y_1=\dfrac{c\cdot y_0}{\gcd(a,b)}$
我们设$d\in Q$，则$a\cdot(x_1+d\cdot b)+b\cdot(y_1-d\cdot a)=c$
显然，$\min\{d\}=\dfrac{1}{\gcd(a,b)}$，设$d_x=d_{\min}\cdot b,d_y=d_{\min}\cdot a$，则通解形式为
CRT
中国剩余定理，用于求解一元模方程组，即模意义下的一元方程组（每个方程的模数不同）
使用CRT的前提是所有模方程的模数互质
即对于
其中$m_1,m_2,…,m_n$两两互质
我们定义$M=\prod m_i$
考虑每一个方程，只要我们能求出$x_i$使得$x_i$是$M_i=\dfrac{M}{m_i}$的倍数且$x_i\equiv 1\pmod{m_i}$，那么最终结果就是$\sum a_i\cdot x_i\bmod M$
然后我们考虑一下我们对$x_i$的定义，我们会惊奇地发现，实际上$x_i=M_i^{-1}\cdot M_i$，其中$M_i^{-1}$为$M_i$在模$m_i$意义下的逆元
所以我们最终的解为$x=\sum a_i\cdot M_i^{-1}\cdot M_i\bmod M$，此处求的是x的最小正整数解，通解$x’=x + k\cdot M$。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
32ll m[N], a[N], M;
ll mul(ll a, ll b) {
ll ans = 0;
for (; b; a = (a << 1) % M, b >>= 1)
if (b & 1)
(ans += a) %= M;
return ans;
}
ll EXGCD(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
ll gcd = EXGCD(b, a % b, x, y), tmpx = x;
x = y;
y = ((tmpx - a / b * y) % M + M) % M;
return gcd;
}
ll CRT() {
ll ans = 0, x, y;
M = 1;
for (int i = 1; i <= n; ++i) {
m[i] = fast_IO::read(), a[i] = fast_IO::read();
M *= m[i];
}
for (int i = 1; i <= n; ++i) {
ll Mi = M / m[i];
EXGCD(Mi, m[i], x, y);//m[i]互质，所以Mi与m[i]互质，满足exgcd的条件
(ans += mul(mul(a[i], x), Mi)) %= M;
}
return ans;
}
exCRT
CRT的使用条件是m[i]互质，如果m[i]不互质，我们引入扩展中国剩余定理。
注意，exCRT的解法是完全跳出CRT思想的，不要认为exCRT是CRT的升级版。
首先我们来考虑只有两个模方程的模方程组
这两个方程显然可以写成
所以有
我们令$m_1\cdot a+m_2\cdot b=\gcd(m_1,m_2)$
由裴蜀定理，当$\gcd(m_1,m_2)\not|(a_1-a_2)$无解，否则$y_1=-\dfrac{a_1-a_2}{\gcd(m_1,m_2)}\cdot a,y_2=\dfrac{a_1-a_2}{\gcd(m_1,m_2)}\cdot b$
我们令$A=a_1+m_1\cdot y_1$，则该模方程组的解为$x\equiv A\pmod{ { \rm{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
31ll mul(ll a, ll b, ll p) {
ll ans = 0;
for (; b; a = (a << 1) % p, b >>= 1)
if (b & 1)(ans += a) %= p;
return ans;
}
ll exGCD(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
ll gcd = exGCD(b, a % b, x, y), tmpx = x;
x = y;
y = tmpx - a / b * y;
return gcd;
}
ll exCRT(int n) {
ll a1 = a[1], m1 = m[1];
for (int i = 2; i <= n; ++i) {
ll a2 = (a[i] % m[i] + m[i]) % m[i], m2 = m[i];
ll del = ((a1 - a2) % m2 + m2) % m2 , x, y;
ll gcd = exGCD(m1, m2, x, y);
m2 /= gcd;
if (del % gcd)return -1;//由裴蜀定理，无解
ll y1 = -mul(x, del / gcd, m2);
a1 += m1 * y1;
m1 = m1 * m2;
a1 = (a1 % m1 + m1) % m1;
}
return a1;
}