最大公约数、同余原理详解
一、最大公约数
（一）欧几里得算法 —— 辗转相除法
欧几里得算法，也被称为辗转相除法，用于计算两个整数的最大公约数，其核心公式为：gcd(a,b) = gcd(b,a mod b)。
以计算 50 和 30 的最大公约数为例：
首先计算50 % 30，得到余数 20，因为余数不为 0，所以继续递归计算gcd(30,20)。
接着计算30 % 20，余数为 10，由于余数仍不为 0，继续递归gcd(20,10) 。
最后计算20 % 10，余数为 0，此时停止递归，gcd(10,0)的结果 10 就是 50 和 30 的最大公约数。
在代码实现上，用 java语言可以一行代码实现：
代码语言：java复制int gcd(int a, int b) {
return b == 0? a : gcd(b, a % b);
}这里利用了递归和三目运算符，当b为 0 时，返回a；否则继续调用gcd函数，将b和a % b作为参数传入。
（二）证明过程
证明思路：
定义与前提：
假设 d 是 a 和 b 的任意一个公因子，即 d | a 且 d | b（表示 d 能整除 a 和 b）。
根据整除的性质，如果 d | a 且 d | b，那么 d 也能整除 a 和 b 的任意线性组合。
证明 d | (a % b)：
已知 a = k * b + r，其中 r = a % b（k 是商，r 是余数）。
因为 d | a 且 d | b，所以 d 能整除 k b（即 d | (k b)）。
根据整除的线性组合性质，d 也能整除 a - k * b，即 d | r。
因此，d 是 b 和 r 的公因子。
反向证明：
假设 m 是 b 和 r 的任意一个公因子，即 m | b 且 m | r。
因为 a = k b + r，且 m | b 和 m | r，所以 m 也能整除 k b + r，即 m | a。
因此，m 是 a 和 b 的公因子。
结论：
由于 a 和 b 的任意公因子 d 也是 b 和 r 的公因子，反之亦然，所以 a 和 b 的公因子集合与 b 和 r 的公因子集合完全相同。
因此，a 和 b 的最大公因子（GCD）等于 b 和 r 的最大公因子，即 gcd(a, b) = gcd(b, a % b)。
（三）时间复杂度
若a > b，欧几里得算法的时间复杂度大致为(O(\log a)^3)。这是因为在每次迭代中，a和b中较大的数至少会变为原来的一半。例如，当a远大于b时，a mod b会使得a在下次递归时大幅减小，经过大约(\log a)次迭代就能得到结果，每次迭代中的运算时间复杂度为(O(\log a)^2)，综合起来整体时间复杂度约为(O(\log a)^3)。
（四）求最小公倍数
两个数a和b的最小公倍数可以通过公式(long)a/gcd(a,b)*b来计算。
原理是：两个数的乘积等于它们的最大公约数和最小公倍数的乘积，即a b = gcd(a,b) lcm(a,b)，所以lcm(a,b) = a b / gcd(a,b)。在代码实现时，为了避免a b可能产生的溢出问题，先进行除法再乘法，即(long)a/gcd(a,b)*b。以 Java 代码为例：
代码语言：java复制public long lcm(long a, long b) {
return (long)a * b / gcd(a, b);
}二、经典习题 ——LeetCode878 第 N 个神奇数字
（一）题目描述
一个正整数如果能被a或b整除，那么它是神奇的。给定三个整数n，a，b，要求返回第n个神奇的数字。由于答案可能很大，所以返回答案对10^9 + 7取模后的值。
（二）解题思路
确定搜索范围：首先，粗略估计第n个神奇数字的范围在(1, n a)。因为假设没有b的影响，第n个神奇数字就是n a，但实际上有b存在，所以搜索范围会缩小。
定义计数函数：定义函数f(x)，用于计算从 1 到x一共有多少个神奇的数字。根据容斥原理，在 1 到x范围内，能被a整除的数字有x / a个，能被b整除的数字有x / b个。然而，有些数字既能被a整除又能被b整除，这些数字被重复计算了，需要减去，而这些数字的个数为x / lcm(a,b) 。所以，f(x) = x / a + x / b - x / lcm(a,b)。
二分答案法求解：利用二分查找的思想，在确定的范围内查找满足f(x) >= n的最小x值。代码如下：
代码语言：java复制class Solution {
public int nthMagicalNumber(int n, int a, int b) {
long lcm = lcm(a, b);
long answer = 0;
for (long l = 0, r = (long)n * Math.min(a, b), m = 0; l <= r;) {
m = (l + r) / 2;
if (m / a + m / b - m / lcm >= n) {
r = m - 1;
answer = m;
} else {
l = m + 1;
}
}
return (int)(answer % 1000000007);
}
public long gcd(long a, long b) {
return b == 0? a : gcd(b, a % b);
}
public long lcm(long a, long b) {
return (long)a * b / gcd(a, b);
}
}在这段代码中，通过二分查找不断调整搜索区间，最终找到满足条件的第n个神奇数字，并对结果取模。
三、其他相关知识
（一）Stein 算法
Stein 算法是一种针对大整数运算的求最大公约数算法，它避免了大整数的除法运算，因为大整数除法运算相对复杂且耗时。该算法主要基于以下几个性质：
若a = b，则gcd(a,b) = a。
若a和b都是偶数，则gcd(a,b) = 2 * gcd(a/2,b/2)。
若a是偶数，b是奇数，则gcd(a,b) = gcd(a/2,b)。
若a是奇数，b是偶数，则gcd(a,b) = gcd(a,b/2)。
若a和b都是奇数，则gcd(a,b) = gcd(|a - b|, min(a,b))。
通过这些性质，不断对大整数进行处理，逐步得到最大公约数，从而提高大整数求最大公约数的效率。
（二）裴蜀定理
裴蜀定理指出，对于任意两个整数a、b，设d = gcd(a,b)，那么关于未知数x和y的线性不定方程ax + by = m有整数解的充要条件是m是d的倍数。特别地，一定存在整数x和y，使得ax + by = d。例如，对于a = 6，b = 9，gcd(6,9) = 3，方程6x + 9y = 3有整数解，如x = -1，y = 1。裴蜀定理在数论、密码学等领域有广泛应用，例如在判断线性同余方程是否有解等问题上发挥重要作用。
四、同余原理
（一）定义
两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m，记作：a≡b (mod m)。例如，7 % 3 = 1，10 % 3 = 1，那么7≡10 (mod 3)。
（二）应用场景
在处理 32 位或 64 位整数时，各种基本运算（加、减、乘、除）的时间复杂度通常为(O(1))。但如果是自己通过字符串转换得到的k位长整数，进行加减操作的时间复杂度为(O(k))，乘除操作的时间复杂度为(O(k²)) 。为了提高运算速度，在中间过程进行取模运算，可将时间复杂度控制在(O(1))，这就是同余原理的重要应用场景。例如在leetcode题目中，要求结果对某个大的素数求%,那么在计算过程中，必须对某个大的素数不断求%。
（三）运算规则
加法同余原理：(a + b) % m的值等于((a % m) + (b % m)) % m。例如，计算(23 + 17) % 5，23 % 5 = 3，17 % 5 = 2，则((23 % 5) + (17 % 5)) % 5 = (3 + 2) % 5 = 0，而直接计算(23 + 17) % 5 = 40 % 5 = 0，结果一致。
乘法同余原理：(a b) % m的值等于((a % m) (b % m)) % m。比如，计算(12 13) % 7，12 % 7 = 5，13 % 7 = 6，那么((12 % 7) (13 % 7)) % 7 = (5 6) % 7 = 30 % 7 = 2，直接计算(12 13) % 7 = 156 % 7 = 2，两者相同。
减法同余原理：(a - b) % m的值等于((a % m) - (b % m) + m) % m ，加上m是为了保证结果一定不是负数，且m % m = 0不会影响最终结果。例如，计算(75 - 17) % 7，75 % 7 = 5，17 % 7 = 3，则((75 % 7) - (17 % 7) + 7) % 7 = (5 - 3 + 7) % 7 = 2，直接计算(75 - 17) % 7 = 58 % 7 = 2，结果相符。
除法同余原理一般较少直接使用，通常会在逆元的知识中进行讲解。逆元是指在模运算下，对于一个整数a和模数m，如果存在整数x使得a * x ≡ 1 (mod m)，那么x就是a关于模m的逆元。在某些需要进行除法模运算的场景中，会借助逆元将除法转换为乘法来处理 。
发布评论