快速幂取模算法

问题引入

快速幂用于求解 $a ^ n mod m$ 的结果。

朴素的做法是直接用循环求解，时间复杂度 $O(n)$。

typedef long long ll;
ll power(ll a, ll n, ll m) {
    ll result = 1;
    for (int i = 0; i < n; ++i) {
        result = (result * a) % m;
    }
    return result;
}

缺点很明显，一是效率低，容易超时，二是指数爆炸，容易爆 $long long$。

阅读全文 »