快速幂_C语言实现

FastPower - 快速幂

在ACM中或有的面试中会考到。核心问题是如何加速算法。

$a^n$即n个a相乘。如何转化？

例：$a^{13_{(10)}}$的计算。

我们可以发现：$a^{4_{(10)}}\cdot a^{4_{(10)}} = (a^{4_{(10)}})^{2_{(10)}} = a^{8_{(10)}}$

更一般地，（以下为10进制）

$$a^1\\ (a^{1})^2 = a^{2}\\ (a^{2})^2 = a^{4}\\ (a^{4})^2 = a^{8}\\ (a^{8})^2 = a^{16}\\ ...$$

则$a^{13_{(10)}}$可以转化为$a^{1101_{(2)}} = a^{8_{(10)}}\cdot a^{4_{(10)}}\cdot a^{1_{(10)}}$，如此，$a^{13_{(10)}}$的计算不用把a傻傻地连乘13次，而是转化为需要计算3个小的数即可。

所以，整个计算过程可以利用前面计算过程中的中间值进行计算，提高效率。

具体算法

把指数看作二进制，对指数最后一位判断是否为1（与1按位与），为1则记录下来处理，之后右移1位，接着判断下一位，如此循环。

long long fast_pow(long a, unsigned n)
{
    long long product = 1;
    while(n)
    {
        if(n & 1)
        {
            product *= a;
        }
        a *= a;  // 每次对应 a^2  a^4  a^8 ...
        n >>= 1;
    }
    return product;
}