快速幂

原理

复杂度：$\Theta (n) \rightarrow \Theta (log_2n)$

$$a^{11}=a^{2^0+2^1+2^3}=a^{2^0} \times a^{2^1} \times a^{2^3}$$

只要把指数位拆分，就可以实现复杂度的骤减。

实现思路

1. 拆分二进制，取出每一位上的值。（移位）
2. 如果值为 1 ，则乘。

实现代码

int fast_pow(int a, int b) {
    int ans = 1, base = a;
    while (b > 0) {
        if (b & 1) ans *= base;
        base *= base;
        b >>= 1;
    }
    return ans;
}

大数取模

原理

$$\left(a\times b\right)\bmod p=\left(a \bmod p\times b\bmod p\right)\bmod p$$

$$\left(a+b\right)\bmod p=\left(a \bmod p+b \bmod p\right)\bmod p$$

实现思路

1. 大数幂取模：乘数取模后相乘再取模。

2. 大数取模：累加时取模。

代码

int fast_pow_mod(int a, int b, int p) {
    int a1 = a, t = 1;
    while (b > 0) {
        if (b & 1)
            t = (t % p) * (a1 % p) % p;
        a1 = (a1 % p) * (a1 % p) % p;
        b>>=1;
    }
    return t % p;
}

int fast_mod(string s, int m) {
    int sum = 0;
    for (auto c:s) {
        sum = (sum * 10 + c - '0') % m;
    }
    return sum;
}