该怎样去加速幂运算的过程呢?既然我们觉得将幂运算分为n步进行太慢,那我们就要想办法减少步骤,把其中的某一部分合成一步来进行。

比如,如果 n 能被 2 整除,那我们可以先计算一半,得到 a^\frac n 2 的值,再把这个值平方得出结果。这样做虽然有优化,但优化的程度很小,仍是线性的复杂度。

再比如,如果我们能找到 2^k=n ,那我们就能把原来的运算优化成 a^1,a^2,a^4,a^8… 只需要 k 次运算就可以完成,效率大大提升。可惜的是,这种条件显然太苛刻了,适用范围很小。不过这给了我们一种思路,虽然我们很难找到 2^k=n 但我们能够找到 2^{k_1}+2^{k_2}+2^{k_3}+……+2^{k_m}=n 。这样,我们可以通过递推,在很短的时间内求出各个项的值。

我们都学习过进制与进制的转换,知道一个 b 进制数的值可以表示为各个数位的值与权值之积的总和。比如, 2 进制数 1001 ,它的值可以表示为 10 进制的 1×2^3+0×2^2+0×2^1+1×2^0 ,即 9 。这完美地符合了上面的要求。 可以通过 2 进制来把 n 转化成 2^{k_m} 的序列之和,而 2 进制中第 i 位(从右边开始计数,值为 1 或是 0 )则标记了对应的 2^{i−1} 是否存在于序列之中。 譬如, 13 为二进制的 1101 ,他可以表示为 2^3+2^2+2^0 ,其中由于第二位为 02^1 项被舍去。

如此一来,我们只需要计算 a^1、a^2、a^4、a^8… a^{2^{k_m}} 的值(这个序列中的项不一定都存在,由 n 的二进制决定)并把它们乘起来即可完成整个幂运算。借助位运算的操作,可以很方便地实现这一算法,其复杂度为 \Omicron(\log n)

long long qpow(long long a, long long n, long long mod) {
    long long res = 1;
    a %= mod;
    while (n) {
        if (n & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return res % mod;
}

发表回复