求最大公约数
1) 欧几里得算法的过程 : 辗转相除法 2) 正确性的证明过程见代码注释部分，润色的证明过程非常好懂，不过直接记忆过程即可 3) 求gcd(a,b)，其中a>b，时间复杂度为O((log a)的3次方)，时间复杂度证明略，这个复杂度足够好了 4) 简单转化就可以求最小公倍数 5) 更高效求最大公约数的Stein算法、由最大公约数扩展出的“裴蜀定理”，比赛同学有兴趣可以继续研究 6) 不比赛的同学，哪怕你的目标是最顶级的公司应聘、还是考研，掌握这个只有一行的函数已经足够！
【总结：】
1.求最大公约数：时间复杂度是\((log(a))^3\)，欧几里得算法/辗转相除法的复杂度足够好了
1
2
3
public long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
2.求最小公倍数：
1
2
3
public long lcm(long a, long b) {
return a / gcd(a, b) * b;
}
力扣878-第 N 个神奇数字
题目
一个正整数如果能被 a 或 b 整除，那么它是神奇的。
给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 10^9 + 7 取模 后的值。
示例 1：
1
2
输入：n = 1, a = 2, b = 3
输出：2
示例 2：
1
2
输入：n = 4, a = 2, b = 3
输出：6
提示：
1 <= n <= 1092 <= a, b <= 4 * 104
解法
思路：二分答案法+容斥原理
要知道\(0～x\)范围上有多少个神奇数字，根据容斥原理，只需要计算\(x/a+x/b-x/lcm(a,b)\)。
根据“二分答案法”，只需要在\([0,n*min(a,b)]\)上寻找。其中n是要寻找的神奇数字的个数。这也很好理解。
代码如下：
注：其中用到的中间的变量都是long类型，不然提交通过不了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int nthMagicalNumber(int n, int a, int b) {
long l = 0, r = (long) n * Math.min(a, b);//范围
long m, ans = 0;
while (l <= r) {
m = l + ((r - l) >> 1);
if (m / a + m / b - m / (lcm(a, b)) >= n){
ans = m;
r = m - 1;
}else {
l = m + 1;
}
}
return (int)(ans % (1000000007));
}
public long gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
public long lcm(int a, int b) {
return a / gcd(a, b) * b;
}
}
同余原理
- 介绍背景
- 加法、乘法每一步计算完后直接取模，减法则为
(a-b+m)%m - 要确保过程中不溢出，所以往往乘法运算的用long类型做中间变量
- 除法的同余需要求逆元，会在【必备】课程里讲述，较难的题目才会涉及
下面是关于上面内容的一些测试代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
import java.math.BigInteger;
public class 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));
}
}
