目录
1. 快速幂
算法原理:
- 计算 311:
- 311 = (35)2 x 3
- 35 = (32)2 x 3
- 32 = 3 x 3
- 仅需计算 3 次,而非 11 次
- 计算 310:
- 310 = (35)2
- 35 = (32)2 x 3
- 32 = 3 x 3
- 仅需计算 3 次,而非 10 次
算法思路:
- 若指数是偶数,则将底数平方,指数除以 2。
- 若指数是奇数,则将底数平方,指数除以 2,再乘上底数。
算法代码:
typedef unsigned long long uLL;
// 快速幂 a^b
uLL power (uLL a, uLL b){
uLL r = 1;
while (b != 0){
if (b & 1) // (b % 2 == 1)
r = r * a;
b = b >> 1; // (b = b / 2)
a = a * a;
}
return r;
}
举例:
- 初始值:a = 3,b = 11
- 第 1 轮:(11 % 2 == 1)r=1x3=3,b=5,a=32=9
- 第 2 轮:(5 % 2 == 1)r=3x32=33=27,b=2,a=(32)2=34=81
- 第 3 轮:(2 % 2 == 0)r 不变,b=1,a=(34)2=38
- 第 4 轮:(1 % 2 == 1)r=33x38=311,b=0,a=(38)2=316
- 得到 r = 33x38 = 311
2. 龟速乘
算法原理:将其中一个乘数分解成 2 的幂次相加。
12 x a = 23 x a + 21 x a
算法代码:
typedef unsigned long long uLL;
// 龟速乘 a*b
uLL mul (uLL a, uLL b){
uLL r = 0;
while (b != 0){
if (b & 1) // (b % 2 == 1)
r = r + a;
b = b >> 1; // (b = b / 2)
a = a + a;
}
return r;
}
3. 快速幂取模
初等数论中有如下公式:
(a × b) % m = ((a % m) × (b % m)) % m
推广:
(a × b × c...) % m = ((a % m) × (b % m) × (c % m) × ... ) % m
(ab) % m = (a × a × a...) % m = ((a % m) × (a % m) × (a % m) × ... ) % m
算法代码:
typedef unsigned long long uLL;
// 快速幂取模 (a^b) % p
uLL powerMod (uLL a, uLL b, uLL p){
uLL r = 1;
while (b != 0){
if (b & 1) // (b % 2 == 1)
r = (r * a) % p;
b = b >> 1; // (b = b / 2)
a = (a * a) % p;
}
return r;
}
4. 龟速乘取模
算法原理:(a × b) % m = ((a % m) × (b % m)) % m
算法代码:
// 龟速乘取模 (a*b) % p
uLL mulMod (uLL a, uLL b, uLL p){
uLL r = 0;
while (b != 0){
if (b & 1) // (b % 2 == 1)
r = (r + a) % p;
b = b >> 1; // (b = b / 2)
a = (a + a) % p;
}
return r;
}
5. 快速幂取模优化
算法原理:注意到快速幂取模算法中的相乘操作可能会超出数据范围,因此可以将相乘操作转化为龟速乘取模。
原理依然是此公式:(a × b) % m = ((a % m) × (b % m)) % m
,其中((a % m) × (b % m))
即为龟速乘取模。
算法思路:快速幂 + 龟速乘结合。
// 快速幂取模防止爆炸 (a^b) % p
uLL powerModBig (uLL a, uLL b, uLL p){
uLL r = 1;
while (b != 0){
if (b & 1) // (b % 2 == 1)
r = mulMod(a, b, p) % p;
b = b >> 1; // (b = b / 2)
a = mulMod(a, a, p) % p;
}
return r;
}
标签:龟速,取模,分治,long,算法,uLL,快速
From: https://www.cnblogs.com/Mount256/p/17159018.html