同余&中国剩余定理&中国剩余定理の扩展
同余
1.线性同余方程
给定整数\(a,b,m\)求一个整数\(x\)满足\(ax \equiv b \pmod m\)，或给出无解。
设\(a \times x = b + my\)，则\(ax + my = b\)，有解的充要条件是\(gcd(a,m)|b\).
接下来只要用exgcd求出一个解，然后就可以求通解了。
2.中国剩余定理
设\(m_1,m_2,m_3,……,m_n\)是两两互质的整数，对于任意的\(n\)个整数\(a_1,a_2,……,a_n\)，关于\(x\)的方程组 \[ \begin{cases} x \equiv a_1 \pmod {m_1}\\x \equiv a_2 \pmod {m_2}\\……\\x \equiv a_n \pmod{m_n}\end{cases} \] 有整数解。
证明：
设\(m = \prod_{i = 1}^nm_i,M_i = m / m_i\)，\(t_i\)是线性同余方程\(M_it_i \equiv 1 \pmod{m_i}\)的一个解。
则\(x_0 = \sum_{i = 1}^n a_iM_it_i\)是一个解
因为\(M_i\)是除了\(m_i\)以外所有数的倍数，所以\(\forall k \neq i,a_iM_it_i \equiv 0 \pmod{m_k}\)。而因为\(M_it_i \equiv 1 \pmod {m_i}\)，所以 $a_iM_it_i a_i $。
这是一个特解。通解为\(x = x_0 + km(k \in Z)\)。
代码
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
using namespace std;
int n,m[30],a[30],M = 1,v[30],t[30],V1,V2;
int exgcd(int a,int b,int &x,int &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int d = exgcd(b,a % b,x,y);
int z = x;
x = y,y = z - (a / b) * y;
return d;
}
signed main() {
scanf("%d",&n);
for (int i=1; i<=n; i++) {
scanf("%d %d",&m[i],&a[i]);
M = M * m[i];
}
for (int i=1; i<=n; i++)
v[i] = M / m[i];
for (int i=1; i<=n; i++) {
int x0,y0;
int gcd = exgcd(v[i],m[i],x0,y0);
x0 %= m[i];
if (x0 <= 0)
x0 += m[i];
t[i] = x0;
}
int sum = 0;
for (int i=1; i<=n; i++)
sum += a[i] * v[i] * t[i];
sum %= M;
if (sum < 0)
sum += M;
printf("%lld\n",sum);
return 0;
}
3.中国剩余定理的扩展版本
上面的方法要求\(m_1,m_2,……,m_n\)两两互质。现在给出一种对\(m_i\)没有要求的算法。
数学归纳法：假设前\(k - 1\)个方程已经求出了一个解\(x\)。记\(m = lcm(m_1,m_2,……,m_{k - 1})\)，则\(x + i \times m (i \in Z)\)是前\(k - 1\)个方程的通解。
考虑第\(k\)个方程，求一个\(t\)，使得\(x + t \times m \equiv a_k \pmod {m_k}\)。将这个方程变换一下，得到\(m \times t \equiv a_{k} - x \pmod {m_k}\),求\(t\). \[ m \times t + m_{k} \times p = a_{k} - x \]