统宗算法(Chinese Remainder Theorem, CRT)是数论中的一个重要定理,它提供了一种解决同余方程组的方法。统宗算法适用于以下形式的同余方程组:
如果有一组同余方程:
```
x ≡ a1 (mod n1)
x ≡ a2 (mod n2)
...
x ≡ ak (mod nk)
```
其中 `n1, n2, ..., nk` 两两互质(即任意两个模数的最大公约数为1),那么这个同余方程组有唯一解模 `N` 的形式,其中 `N = n1 * n2 * ... * nk`。
统宗算法的步骤如下:
1. 计算所有模数的乘积 `N = n1 * n2 * ... * nk`。
2. 对于每个同余方程 `x ≡ a (mod n)`,计算 `Ni = N / ni`,即 `N` 除以当前的模数 `ni`。
3. 对于每个 `Ni`,找到它的乘法逆元 `yi`,使得 `Ni * yi ≡ 1 (mod ni)`。
4. 计算 `x` 的解 `x = (a1 * N1 * y1 + a2 * N2 * y2 + ... + ak * Nk * yk) mod N`。
统宗算法的题目通常要求应用这个定理来解决具体的同余方程组问题。以下是一个简单的统宗算法题目示例:
**题目**:
给定一组同余方程:
```
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
```
求解 `x`。
**解答**:
首先计算所有模数的乘积 `N = 3 * 5 * 7 = 105`。
然后计算每个 `Ni` 和对应的乘法逆元 `yi`:
```
N1 = N / 3 = 105 / 3 = 35, y1 = 2 (因为 35 * 2 ≡ 1 (mod 3))
N2 = N / 5 = 105 / 5 = 21, y2 = 1 (因为 21 * 1 ≡ 1 (mod 5))
N3 = N / 7 = 105 / 7 = 15, y3 = 1 (因为 15 * 1 ≡ 1 (mod 7))
```
最后计算 `x` 的解:
```
x = (2 * 35 * 2 + 3 * 21 * 1 + 2 * 15 * 1) mod 105
x = (140 + 63 + 30) mod 105
x = 233 mod 105
x = 23
```
所以,这个同余方程组的解是 `x ≡ 23 (mod 105)`。