# 快速乘
将 B
二进制展开,如果 B
的二进制表示下第 i 位为 1(i从0开始),那么这一位对最后结果的贡献就是 A*(1<<i)*,即 A<<i 。这个方法经常被用于两数相乘取模的场景,如果两数相乘已经超过数据范围,但取模后不会超过,我们就可以利用这个方法来拆位取模计算贡献,保证每次运算都在数据范围内。
int quickMulti(int A, int B) {
int ans = 0;
for ( ; B; B >>= 1) {
if (B & 1) {
ans += A;
}
A <<= 1;
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 快速幂
对于幂运算ab来说,如果用for循环将1乘上a,循环b次,时间复杂度基于b,使用快速幂可使时间复杂度降为O(1),将 b
二进制展开,如果 b
的二进制表示下第 i 位为 1(i从1开始),那么这一位对最后结果的贡献就是ai,将这些贡献累乘即可。
public int pow(int a, int b) {
int base = a, ans = 1;
for (; b != 0; b >>= 1) {
if ((b & 1) == 1) {
ans *= base;
}
base *= base;
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 最大公约数和最小公倍数
// 辗转相除法求最大公约数
// 18 / 12 = 1 ... 6
// 12 / (6) = 2 ... 0
public static int gcd(int a, int b){
if(b == 0)
return a;
return gcd(b, a % b);
}
// 最小公倍数
public static int lcm(int a, int b){
return a * b / gcd(a, b);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13