深圳网站开发哪个好,自动推送百度wordpress,网站设计机构有哪些,互联网黄页是什么1. 辗转相除法
对下面的证明过程有什么问题和怀疑的直接随便找两个数字自己写一遍就行了.
1.1 利用辗转相除法计算最大公约数
直接记忆这段代码公式就行了(具体的证明过程直接去看左程云老师写的就行了).
public static long gcd(long a, long b) { // Greatest Common Di…
1. 辗转相除法
对下面的证明过程有什么问题和怀疑的直接随便找两个数字自己写一遍就行了.
1.1 利用辗转相除法计算最大公约数
直接记忆这段代码公式就行了(具体的证明过程直接去看左程云老师写的就行了).
public static long gcd(long a, long b) { // Greatest Common DivisorGCD 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 MultipleLCM 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 这几个数字中.
我们先找能整除 a 的数字有几个x / a 个 2, 4, 6, 8, 10.然后找能整除 b 的数字有几个x / b 个 3, 6, 9.肯定是有重复的值比如说6.因为一个数字只能是一个神奇的数字, 所以重复的情况是x / lcm(a, b).(这个函数之前讲解过).最后得到的是神奇的数字的个数为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 类型能表示的范围, 若是用这个数字进行运算, 这样会大大增加时间复杂度. 那么我们如何规避这样的情况, 这就用到了同余原理.\
同余原理解决两个问题
真实结果 % mod ? 如何保证 ? 是对的.保证 , -, * / 运算的常数时间.
注意我们平时在进行加减乘除运算的时候, 无论是 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)); } }
