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

快速幂

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

$$a ^ b = a ^ {\frac{b}{2}} \times a ^ {\frac{b}{2}}$$

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为偶数时

$$a \times b = a \times 2 \times \frac{b}{2}$$

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

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;
}

等比数列求和

对于一个等比数列

$$p^0 + p^1 + p^2 + ...+ p^n \text{(共k=n+1项)}$$

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

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

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

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

当k为偶数时, 可知

$$p^0 + p^1 + p^2 + ...+ p^n = (p^0 + p^1 + ... + p^{k/2-1}) + (p^{k/2}+...+p^n)$$

此时可化为

$$=(1+p^{k/2})(p^0 + p^1 + ... + p^{k/2-1})$$

我们用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)

代码:

// 求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;
}