class 041 最大公约数、同余原理

1. 辗转相除法

对下面的证明过程有什么问题和怀疑的直接随便找两个数字自己写一遍就行了.

1.1 利用辗转相除法计算最大公约数

直接记忆这段代码公式就行了(具体的证明过程直接去看左程云老师写的就行了).

public static long gcd(long a, long b) {  // Greatest Common Divisor，GCD  return b == 0 ? a : gcd(b, a % b);  // 需要注意的是 a > b
}

这个的时间复杂度是：log(n) ^ 3. 已经足够好了.

1.2 利用辗转相除法计算最小公倍数

也是直接记忆就行, 证明更简单, 不用说

public static long lcm(long a, long b) {  // Least Common Multiple，LCM  return (long) a / gcd(a, b) * b;  
}

2. 题目练习：第 n 个神奇的数字

2.1 题目描述

https://leetcode.cn/problems/nth-magical-number/

2.2 逻辑实现

这里我们会利用“二份答案法”和“容斥原理”, 但是都是非常简单的情况, 不用系统了解学习也能理解.

首先我们假设有 a = 2, b = 3 这两个数字, 我们要找第 100 个(n = 100)神奇的数字, 那么这个神奇的数字一定在 [1, n * min(a, b)] 之间, 因为：我们假设没有 b 这个数字, 那么第一百个神奇的数字肯定是 200, 此时有了 b = 3 这个数字了, 比如 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. 原来 [1, 10] 之间只有 2, 4, 6, 8, 10 这 5 个神奇的数字, 那么有了 3 之后, 至少新增加了一个 3, 那么第一百个神奇的数字肯定在 [1, 200] 之间了.

神奇的数字怎么求解：a = 2, b = 3. 在 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 这几个数字中.

1. 我们先找能整除 a 的数字有几个：x / a 个 2, 4, 6, 8, 10.
2. 然后找能整除 b 的数字有几个：x / b 个 3, 6, 9.
3. 肯定是有重复的值：比如说：6.
4. 因为一个数字只能是一个神奇的数字, 所以重复的情况是：x / lcm(a, b).(这个函数之前讲解过).
5. 最后得到的是神奇的数字的个数为：x / a + x / b - x / lcm(a, b).

然后我们假设有一个 f(x) 函数, 这个函数能判断出来 <= x 的范围内, 有几个神奇的数字, 我们假设要在 [1, 200] 之间找第 n 个神奇的数字, 先是 100, 若是发现不够(< n), 就去右边找：150, 若是够了, 就在 [100, 150] 之间找到尽量小的的位置. 比如说到了 140 够了, 139 不够, 那么说明 140 肯定就是我们需要的第 n 个有效数字了.

具体例子：下面这个例子中, 答案是 8.

2.3 代码实例

该有的注释我都写到了代码中.

Code02_NthMagicalNumber {  public static void main(String[] args) {  int n = 3;  int a = 4;  int b = 6;  System.out.println(nthMagicalNumber(3, 4, 6));  }  public static int nthMagicalNumber(int n, int a, int b) {  long lcm = lcm(a, b); // 先找到a, b的最小公倍数.  long ans = 0;  // l = 0  // r = (long) n * Math.min(a, b)      // l......r       long l = 0, r = (long) n * Math.min(a, b), m = 0;  while (l <= r) {  m = (l + r) / 2;  // 1....m  // 这样写的原因是有可能在其中一个比较大的范围上也是和答案一样的.  // 比如上面n = 3, a = 4, b = 6 的情况下,  // 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12.          // 在这几个数字的范围中, 8 是第三个神奇的数字, 但是 9 不是一个神奇数字, 但是当 m == 9 的时候  // m / a + m / b - m / lcm == n, 所以最后会返回 9, 这是不对的.  // 所以要继续往下走.  // 不能修改为这样的代码：
//        if (m / a + m / b - m / lcm > n) {
//           r = m - 1;  
//        } else if (m / a + m / b - m / lcm < n){  
//           l = m + 1;  
//        } else {  
//           ans = m;  // 此时遇到对应的值就返回了, 按照上面的例子, 最后返回的是 9, 但是正确答案是 8, 
//           break;  
//        }if (m / a + m / b - m / lcm >= n) {  ans = m;  r = m - 1;  } else {  l = m + 1;  }  }  return (int) (ans % 1000000007);  }  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 (long) a / gcd(a, b) * b;  }  }

3. 同余原理 (加法, 减法, 乘法)

假设我们现在面临一个情况：我们得到的值已经远远超出 long 类型能表示的范围, 若是用这个数字进行运算, 这样会大大增加时间复杂度. 那么我们如何规避这样的情况, 这就用到了同余原理.\

同余原理解决两个问题：

1. 真实结果 % mod == ? 如何保证 ? 是对的.
2. 保证 +, -, * / 运算的常数时间.

注意：我们平时在进行加减乘除运算的时候, 无论是 int(32位)还是long(64位) 类型的, 都默认的时间复杂度是 O(1).
但是若是 k位 数字的 +, - 时间复杂度是：O(k), * / 的时间复杂度是：O(k^2).

除法的同余原理需要用到逆元, 比较麻烦, 会放到后面.

3.1 加法的同余原理

比如 (a + b) + (c + d) = ans,我们假设 a + b == ans1, c + d = ans2, ans1 + ans2 == ans3.
那么：ans % mod == ans3 % mod, ans1 % mod + ans2 % mod == ans % mod.

只需要记住就行了, 自己可以尝试带入几个具体的案例

3.2 乘法的同余原理

乘法的同余原理和加法是一样的.

3.3 减法的同余原理

首先, 我们需要先明确一个前提, 我们接受的余数只能是非负数.

举一个例子：(75 - 17) % 7 == 58 % 7 == 2 那么利用同余原理：75 % 7 == 5, 17 % 7 == 3, 所以 (5 - 3) % 7 == 2, 这样最后的结果是对的, 但是其实会有问题, 有可能余数为负数.

比如：(72 - 18) % 7 == 5, 72 % 7 == 2, 18 % 7 == 4, 这样 (2 - 4) % 7 == -2, 我们刚刚说过, 是不能有负数的, 所以我们需要修改一下, 修改为：(2 - 4 + 7) % 7 == 5, 这样的最后结果才是正确的,

所以第一个例子中, 我们应该让其加上 mod 再取模：(5 - 3 + 7) % 7 == 2, 最后的结果还是正确的, 所以正确的方式应该是 (a - b) % mod == (a % mod - b % mod + m) % m.

3.4 验证同余原理的正确性(没有除法的同余原理)

// 加法、减法、乘法的同余原理  
// 不包括除法，因为除法必须求逆元，后续课讲述  
public class Code03_SameMod {  // 为了测试  public static long random() {  return (long) (Math.random() * Long.MAX_VALUE);  }  // 计算 ((a + b) * (c - d) + (a * c - b * d)) % mod 的非负结果  public static int f1(long a, long b, long c, long d, int mod) {  BigInteger o1 = new BigInteger(String.valueOf(a)); // a  BigInteger o2 = new BigInteger(String.valueOf(b)); // b  BigInteger o3 = new BigInteger(String.valueOf(c)); // c  BigInteger o4 = new BigInteger(String.valueOf(d)); // d  BigInteger o5 = o1.add(o2); // a + b  BigInteger o6 = o3.subtract(o4); // c - d  BigInteger o7 = o1.multiply(o3); // a * c  BigInteger o8 = o2.multiply(o4); // b * d  BigInteger o9 = o5.multiply(o6); // (a + b) * (c - d)  BigInteger o10 = o7.subtract(o8); // (a * c - b * d)  BigInteger o11 = o9.add(o10); // ((a + b) * (c - d) + (a * c - b * d))  // ((a + b) * (c - d) + (a * c - b * d)) % mod       BigInteger o12 = o11.mod(new BigInteger(String.valueOf(mod)));  if (o12.signum() == -1) {  // 如果是负数那么+mod返回  return o12.add(new BigInteger(String.valueOf(mod))).intValue();  } else {  // 如果不是负数直接返回  return o12.intValue();  }  }  // 计算 ((a + b) * (c - d) + (a * c - b * d)) % mod 的非负结果  public static int f2(long a, long b, long c, long d, int mod) {  int o1 = (int) (a % mod); // a  int o2 = (int) (b % mod); // b  int o3 = (int) (c % mod); // c  int o4 = (int) (d % mod); // d  int o5 = (o1 + o2) % mod; // a + b  int o6 = (o3 - o4 + mod) % mod; // c - d  int o7 = (int) (((long) o1 * o3) % mod); // a * c  int o8 = (int) (((long) o2 * o4) % mod); // b * d  int o9 = (int) (((long) o5 * o6) % mod); // (a + b) * (c - d)  int o10 = (o7 - o8 + mod) % mod; // (a * c - b * d)  int ans = (o9 + o10) % mod; // ((a + b) * (c - d) + (a * c - b * d)) % mod  return ans;  }  public static void main(String[] args) {  System.out.println("测试开始");  int testTime = 100000;  int mod = 1000000007;  for (int i = 0; i < testTime; i++) {  long a = random();  long b = random();  long c = random();  long d = random();  if (f1(a, b, c, d, mod) != f2(a, b, c, d, mod)) {  System.out.println("出错了!");  }  }  System.out.println("测试结束");  System.out.println("===");  long a = random();  long b = random();  long c = random();  long d = random();  System.out.println("a : " + a);  System.out.println("b : " + b);  System.out.println("c : " + c);  System.out.println("d : " + d);  System.out.println("===");  System.out.println("f1 : " + f1(a, b, c, d, mod));  System.out.println("f2 : " + f2(a, b, c, d, mod));  }  }