几种运算中基于分治的优化

本文最后更新于:2022年8月17日 上午

快速幂

众所周知, 快速幂主要基于平方法进行优化, 当指数为偶数的时候

1
2
3
4
5
6
7
8
9
ll qpow(ll x, ll y, ll mod)  {
ll ans = 1;
while (y) {
if(y & 1) ans = ans * x % mod;
x = x * x % mod;
y >>= 1;
}
return ans;
}

龟速乘

龟速乘主要用来解决两个数相乘直接爆long long的问题

比如这题: https://www.acwing.com/problem/content/92/

思想和快速幂基本一致, 即当b为偶数时

换句话说, 即用二进制的思想, 对64位整数b, 我们循环他的每一个二进制位, 第n位为1就加上$2^n \times a$即可

1
2
3
4
5
6
7
8
9
10
11
ll qadd(ll a, ll b, ll mod) {
ll ans = 0;
while (b) {
if (b & 1) {
ans = (ans + a) % mod;
}
a = (a + a) % mod;
b >>= 1;
}
return ans;
}

等比数列求和

对于一个等比数列

当n非常大, 我们需要对答案取mod

首先可以利用等比数列求和公式解决取模的问题, 不过需要考虑逆元

现在来考虑用分治的方法解决这个问题

首先分情况讨论k为奇和偶

当k为偶数时, 可知

此时可化为

我们用sum(p, k - 1)来表示$p^0 + p^1 + p^2 + …+ p^n$

即当k为偶数时sum(p, k) = sum(p, k / 2) * (1 + qpow(p, k / 2))

当k为奇数时很简单, 只需要将第一项或者最后一项拿出, 再把剩余部分当作偶数情况考虑即可, 我们这里选择将最后一项拿出,

即当k为奇数时sum(p, k) = sum(p, k - 1) + qpow(p, k - 1)

代码:

1
2
3
4
5
6
7
8
9
10
11
// 求a^0 + a^1 + a^2 + ... + a^(b - 1)
ll sum (ll a, ll b) {
ll ans = 0;
if (b < 1) return 0;
if (b & 1) {
ans = sum(a, b - 1) + qpow(a, b - 1);
} else {
ans = (1 + qpow(a, b / 2)) * sum (a, b / 2);
}
return ans % mod;
}

几种运算中基于分治的优化
https://blog.roccoshi.top/posts/51222/
作者
RoccoShi
发布于
2021年7月20日
许可协议