扩展的中国剩余定理
中国剩余定理
中国剩余定理最早由中国古代数学家孙子（孙秀英）在《孙子算经》一书中提出。这本书是中国古代数学的重要著作之一，成书于4世纪至5世纪之间。
中国剩余定理是一种用于求解一类线性同余方程组的定理。线性同余方程组是指形式为x ≡ b1 (mod n1), x ≡ b2 (mod n2), ..., x ≡ br (mod nr)的方程组，其中x是未知数，bi是已知的整数，ni是不同的正整数。
中国剩余定理的由来是为了解决天文学和农业中的一些实际问题。古代中国天文学家需要根据观测得到的数据计算出各种天文现象的时间和位置，而农业中也需要根据天文观测来确定农作物的种植时间。而孙子在研究天文学和农业问题中，发现了这个定理。
中国剩余定理的核心思想是，如果给定了一组同余方程的解，那么可以通过合理地选择不同模数的倍数，使得这些同余方程的解对应的数的和仍然满足同余关系。通过这种方式，可以得到一组满足同余关系的解，并且能够覆盖所有可能的解。
中国剩余定理在中国古代的科学与数学研究中起到了重要的作用，并且在后来的数学研究中被广泛应用。它不仅解决了古代天文学和农业中的实际问题，还为数论和代数学的研究提供了重要的思路和方法。
拓展欧几里得算法
拓展欧几里得算法（Extended Euclidian Algorithm），是欧几里得算法的扩展版本，用于在计算两个数的最大公约数 gcd ( a , b ) \gcd(a, b)gcd(a,b) 的同时，找到这两个整数的 贝祖系数（即这两个整数的线性组合等于其最大公约数的系数）。
举例而言，如果给定两个整数 a , b a, ba,b，我们不仅可以找到这两个整数的最大公约数，还可以找到两个整数 x , y x, yx,y，满足：ax+by=gcd(a,b)
与此同时，我们也将这个方程称之为 贝祖等式 （Bézout’s identity）。拓展欧几里得算法在数论和计算机应用方面有着极其突出的贡献和广泛的应用。例如求解线性同余方程，本文也将会围绕求解同余方程来展开。
逆元
在数学中，特别是在数论和抽象代数中，逆元（或逆元素）是指与某个元素相乘（或进行其他某种运算）后得到乘法单位元（或相应的运算单位元）的元素。具体来说：
乘法逆元
对于乘法，如果有一个元素 a 和一个乘法单位元 1（通常是整数乘法中的1，或者是群、环或域中的单位元素），那么 a 的乘法逆元是一个元素 b，使得 a * b = b * a = 1。在这种情况下，我们通常将 b 记作 a 的逆元，写作 a^-1。
例如：
- 在整数集合中，除了0以外的每个整数 a 在模 m 的意义下都有一个乘法逆元，前提是 a 和 m 互质。这个逆元是另一个整数 b，使得 (a * b) % m = 1。
- 在实数集合中，除了0以外的每个实数 a 都有一个乘法逆元，即 1/a，因为 a * (1/a) = 1。
加法逆元
对于加法，如果有一个元素 a 和一个加法单位元 0（通常是加法中的0），那么 a 的加法逆元是一个元素 -a，使得 a + (-a) = (-a) + a = 0。
例如：
- 在整数集合中，每个整数 a 都有一个加法逆元 -a，因为 a + (-a) = 0。
逆元的计算
在扩展欧几里得算法中，我们寻找两个整数 a 和 m 的乘法逆元，即找到一个整数 x，使得 (a * x) % m = 1。这个 x 就是 a 在模 m 下的乘法逆元。
乘法逆元的作用
乘法逆元在数学和密码学中非常重要，特别是在解决模线性方程时。一个整数 a 在模 m 下的乘法逆元是一个整数 x，使得：
(a * x) % m = 1
换句话说，x 是 a 在模 m 下的逆元，如果它们相乘然后取模 m 的结果为 1。乘法逆元的主要用途包括：
- 解模线性方程 ：例如，要解方程 ax ≡ b (mod m)，如果 a 有乘法逆元，我们可以将方程两边乘以 a 的逆元来找到 x。
- 密码学 ：在 RSA 加密算法中，乘法逆元用于解密过程
乘法逆元的概念
想象你在玩一个数字游戏，规则是这样的：你有一个数字 a，你需要找到一个数字 x，使得当你用 a 乘以 x，然后对某个数字 m 取余数时，结果是 1。这个数字 x 就是 a 在模 m 下的乘法逆元。
举个例子，如果 a 是 3，m 是 11，你需要找到一个 x 使得 (3 * x) % 11 = 1。在这个例子中，x 是 4，因为 (3 * 4) % 11 = 12 % 11 = 1。
乘法逆元的作用就像是数字的“反操作”，类似于加法的相反数。如果你有一个数字加上它的相反数，结果是 0；同样地，如果你有一个数字乘以它的乘法逆元，结果是 1（在模 m 下）。
扩展的中国剩余定理（EXCRT）的原理
中国剩余定理是一个古老的方法，用于解决一系列的同余方程。EXCRT 是这个方法的扩展，它允许我们解决当模数不互质时的同余方程组。
原理解释
起始点 ：想象你有几个盒子，每个盒子都有一个数字，你需要找到一个数字，这个数字在每个盒子中的余数都符合要求。
合并盒子 ：你从第一个盒子开始，假设你找到了一个数字 x，它在第一个盒子中的余数是 a1。现在，你想要找到一个数字，它在第二个盒子中的余数是 a2，同时还要保持第一个盒子的余数不变。
乘法逆元的作用 ：为了合并第二个盒子的条件，你需要找到一个方法来“调整”数字 x，使得它同时满足第一个和第二个盒子的条件。这就是乘法逆元的作用。你找到一个数字，它可以让你在不改变第一个盒子条件的情况下，调整 x 以满足第二个盒子的条件。
重复过程 ：你对每个盒子重复这个过程，每次都找到一个乘法逆元来调整 x，直到所有的盒子条件都被满足。
代码的思路：
初始化 ：从第一个同余方程开始，设置初始解 ans 为 a[0]，初始模数 M 为 m[0]。
迭代合并同余方程 ：
* 对于每个同余方程（从第二个开始），计算 Mi，它是当前 M 除以当前模数 m[i] 的最大公约数。
* 使用扩展欧几里得算法找到 Mi 相对于 m[i] 的乘法逆元 x。
* 计算 x，确保其为正数，并将其用于更新解 `ans`。
* 更新 M 为所有已处理模数的乘积除以它们的 GCD。
* 保持 `ans` 在正确的范围内（非负且小于 M）。返回结果 ：在所有同余方程都合并后，返回最终的解 ans。
代码中的关键步骤
- 计算 Mi ：这是为了找到一个数，它与当前的模数 m[i] 互质，这样我们就可以找到乘法逆元。
- 找到乘法逆元 ：这允许我们将新同余方程合并到当前解中。
- 更新解 ：通过乘法逆元和 Mi，我们可以调整当前解，使其同时满足新同余方程。
public class ExtendedChineseRemainderTheorem {
// 扩展欧几里得算法，返回gcd(a, b)，并计算x, y使得ax + by = gcd(a, b)
private static int extendedGcd(int a, int b, int[] xy) {
if (a == 0) {
xy[0] = 0;
xy[1] = 1;
return b;
}
int[] x1y1 = new int[2];
int gcd = extendedGcd(b % a, a, x1y1);
xy[0] = x1y1[1] - (b / a) * x1y1[0];
xy[1] = x1y1[0];
return gcd;
}
// 扩展的中国剩余定理
public static int excrt(int[] a, int[] m) {
int n = a.length;
long ans = a[0];
long M = m[0];
for (int i = 1; i < n; i++) {
int Mi = M / gcd(M, m[i]);
int[] xy = new int[2];
extendedGcd(Mi, m[i], xy);
long x = xy[0];
// 确保x为正数
x = (x % m[i] + m[i]) % m[i];
// 更新答案
ans += (a[i] - ans % m[i] + m[i]) % m[i] * Mi * x;
M *= m[i] / gcd(M, m[i]);
ans = (ans % M + M) % M;
}
return (int) ans;
}
// 计算最大公约数
private static int gcd(long a, long b) {
return b == 0 ? (int) a : gcd(b, a % b);
}
public static void main(String[] args) {
int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1};
int[] m = {10, 9, 8, 7, 6, 5, 4, 3, 2};
int result = excrt(a, m);
System.out.println("The solution is: " + result);
}
}