快速幂
求 $3^{13}$
普通方法
- 常规算法
$3^{13}$ = $3·3·3·3·3·3·3·3·3·3·3·3·3$
需要算 $14$ 次
- 二分法
typedef long long ll;
ll power(int x, int y) {
if(y & 1) {
return x * power(x, y-1);
}
return power(x * x, y/2);
}
快速
$(13)_{10}$ = $(1101)_2$ = $1$·$2^3$ + $1$·$2^2$ + $0$·$2^1$ + $1$ · $2^0$
$3^{13}$ = $3^{1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0}$
$3^{13}$ = $3^8$ · $3^4$ · $3^1$
只需要算 $7$ 次
| 循环次数 | 底数 | 指数(二进制) | 结果值 |
|---|---|---|---|
| $1$ | $3^1$ | $1101$ | $3^1$ |
| $2$ | $3^2$ | $110$ | $3^1$ |
| $3$ | $3^4$ | $11$ | $3^1$ * $3^4$ |
| $4$ | $3^8$ | $1$ | $3^1$ * $3^4$ * $3^8$ |
快速幂就是对底数进行平方, 遍历指数的每一位, 若指数当前位为 1, 保存当前底数的乘积
typedef long long ll;
// x为底数, y为指数
ll FastPower(ll x, ll y, ll mod) {
if (y == 0) {
return 1;
}
ll r = 1;
while (y) {
// 指数当前位为1, 保存底数乘积
if (y & 1) {
r = (r * x) % mod;
}
y >>= 1;
// 底数做平方运算
x = (x * x) % mod;
}
return r;
}
优化 快速乘
long long FastMul(int x, int y) {
long long r = 0;
while (y) {
if (y & 1) {
r += x;
}
y >>= 1;
x <<= 1;
}
return r;
}
下篇欧拉函数