快速幂取模算法

问题引入

快速幂用于求解 $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$。

快速幂 分治思想

可以将问题分解成如下的子问题：

$$a^n\ mod\ m = \begin{cases} 1\ mod\ m, & n = 0\\ (a^{n/2} \cdot a^{n/2}) \ mod\ m, & n是偶数\\ (a \cdot a^{n/2} \cdot a^{n/2})\ mod\ m, & n是奇数 \\ \end{cases}$$

写成递归的形式

$$power(a, n, m) = \begin{cases} 1\% m, & n = 0\\ power(a^2, n/2, m) \% m, & n是偶数\\ (a * power(a^2, n/2, m)) \% m, & n是奇数 \\ \end{cases}$$

代码如下

typedef long long ll;
ll quick_mod(ll a, ll n, ll m) {
    if (n == 0)
        return 1;
    else if (n % 2 == 0) 
        return quick_mod(a * a, n / 2, m) % m;
    else 
        return ((a % m) * quick_mod(a * a, n / 2, m)) % m;
}

上述代码就是快速幂了。

朴素方法计算 $a ^ n$ 其实计算了两遍 $a ^ {n / 2}$ 再相乘，其实计算一次 $a ^ {n / 2}$ 就够了，因为 $a ^ {n / 2}$ 的平方就是 $a ^ n$。而计算 $a ^ {n / 2}$ 又等价于计算 $a ^ {n / 4}$ 的平方…，因此只需 $log(n)$ 次就可以计算出结果。采用分而治之的方法将时间复杂度降为 $O(log(n))$。

由于递归比较慢，且容易爆栈，因此改成非递归的形式。

typedef long long ll;
ll quick_mod(ll a, ll n, ll m) {
    if(n == 0)
        return 1 % m;

    ll res = 1;
    while (n > 0) {
        if (n % 2 == 0) { 
            a = (a * a) % m;
            n = n / 2;
        } else {
            res = (res * a) % m;
            a = (a * a) % m; 
            n = n / 2;
        }
    }
    return res;
}

可以发现上述代码有重复部分，还可以简化。

typedef long long ll;
ll quick_mod(ll a, ll n, ll m) {
    if(n == 0)
        return 1 % m;

    ll res = 1;
    while (n > 0) {
        if(n % 2) { 
            res = (res * a) % m;
        }
        a = (a * a) % m; 
        n = n / 2;
    }
    return res;
}

进一步优化

typedef long long ll;
ll quick_mod(ll a, ll n, ll m) {
    if(!n)
        return 1 % m;

    ll res = 1;
    while (n) {
        if(n & 1) {  // 二进制最后一位为 1是奇数
            res = (res * a) % m;
        }
        a = (a * a) % m; 
        n >>= 1;  // 右移一位就是整除 2
    }
    return res;
}

相关题目

• POJ 1995