算法（三）——最大公约数、最小公倍数、同余原理

文章目录

最大公约数、最小公倍数、同余原理
- 最大公约数
- 最小公倍数
- 同余原理

最大公约数、最小公倍数、同余原理

最大公约数

最大公约数的计算可以采用 欧几里得算法（辗转相除法），基本思想是：两个整数的最大公约数等于其中较小的数和两数相除的余数的最大公约数。这个过程一直重复，直到余数为0，此时的除数就是最大公约数。

代码样例：

    public static long gcd(long a, long b) {return b == 0 ? a : gcd(b, a % b);}

最小公倍数

在求得最大公约数的基础上，可以很容易地求出最小公倍数，代码如下：

    public static long lcm(long a, long b) {return a * b / gcd(a, b);}

【经典例题】

原题链接：878. 第 N 个神奇数字 - 力扣（LeetCode）

在这里插入图片描述

根据题目要求，神奇数字是一个正整数，因此要从 1 开始考虑。以示例二为例，要求求出第4个神奇数字，从1开始，2能被2整除是第一个神奇数字，3能被3整除是第二个神奇数字，4能被2整除是第三个神奇数字，5不是神奇数字，6既能被2整除也能被3整除因此是第四个神奇数字，答案是6。

由于参数的随机性，我们每次都要从1开始考虑，范围太大了，因此我们考虑缩小范围：第 n 个神奇数字的范围：[1, min(a, b) * n]，因为能被 a 整除或者能被 b 整除的数一定是神奇数字，所以范围的上界可以缩小到 a 和 b 较小值的 n 倍。

确定的范围是有序的，考虑二分加快效率，二分依据什么？ 考虑[1, min(a, b) * n]区间内的一个数num，我们能否得到[1, num]范围内有几个神奇数字？如果能够求出，我们就可以在[1, min(a, b) * n]区间二分，每次判断中间值num（num其实就是每次二分求得的mid）在[1, num]范围内有几个神奇的数字，与n对比：如果比n小，说明[1, num]范围内不会出现第n个神奇数字，要在(num, right]寻找；如果比n大或者等于n说明[1, num]中包含第n个神奇的数字。（注意：等于的情况下，num的值不一定是第n个神奇的数字，例如：当n = 3；a = 6；b = 4时，第n个神奇的数字应该是8，但是对于数字num = 9，也满足[1, num]范围内的神奇数字等于n ，我们必须找到大于或等于 n 的最小的 num）。

那么，如何求[1, num]范围内有几个神奇数字呢？

数量count = num / a + num / b - num / a和b的最小公倍数，即范围内能被a整除的数量 + 范围内能被b整除的数量 - 重复计算的数量（范围内能被a和b的最小公倍数整除的数量）

【代码实现】

class Solution {public int nthMagicalNumber(int n, int a, int b) {long l = 1;long r = Math.min(a, b) * (long) n;long ret = 0;long lcmNum = lcm(a, b);while(l <= r) {long m = (l + r) / 2;long count = m / a + m / b - m / lcmNum;if(count >= n) {ret = m;r = m - 1;}else {l = m + 1;}}return (int) (ret % 1000000007);}private static long gcd(long a, long b) {return b == 0 ? a : gcd(b, a % b);}private static long lcm(long a, long b) {return a * b / gcd(a, b);}
}

使用1000000007而非(long) (10e9 + 7)，这会导致类型转换和精度问题。

同余原理

我们这里言简意赅，介绍一下算法中同余原理的常见应用场景以及常用结论：

应用场景
- 避免大数运算：在算法竞赛中，经常需要处理非常大的数。直接对大数进行运算可能会导致溢出或计算效率低下。同余原理允许我们在计算过程中不断取模，将大数问题转化为小数问题，从而避免溢出并提高计算效率。
- 数论问题：许多算法竞赛题目涉及数论，如最大公约数、最小公倍数、素数判定等。同余原理是解决这些数论问题的基础工具。
常用结论
- 加法同余原理：多个数的和对一个数取模得到的余数，等于每个数对相同的数取模得到的余数相加后再对这个数取模。
  
  (a + b) % mod = (a % mod + b % mod) % mod
- 乘法同余原理：多个数的乘积对一个数取模得到的余数，等于每个数对相同的数取模得到的余数的乘积再对这个数取模。
  
  (a * b) % mod = (a % mod * b % mod) % mod
- 减法同余原理：多个数的差对一个数取模得到的余数，等于每个数对相同的数取模得到的余数的差，再加上模数后再对这个数取模。
  
  (a - b) % mod = (a % mod - b % mod + mod) % mod

简单说明：

三种同余原理的右边部分再次% mod是为了确保最终的余数在0 ~ mod - 1的范围内
对于减法同余原理，再次+ mod是为了避免结果为负数，因为题目一般要求得到非负结果
注意两个操作数a和b相加和相乘的结果可能溢出int，因此我们要强制类型转换为long，取模后再转换为int

例如：int ret = (int) (((long) a * b) % mod)
总之，如果要求返回一个复杂表达式的结果取模后的非负结果，并且表达式的操作数是大数，此时我们就可以利用同余定理化简计算。