算法1.快速幂【a^b、(a^b)%p】

算法1.快速幂($a^b$、$a^b\%p$)

快速幂是一个很常见的算法，该算法主要求解的是$a^b$类型的运算，这样的运算往往数据类型会比较大，所以会导致越界，所以结果往往是按照取模给出，即$(a^b)\%c$.在接触快速幂之前，首先要了解一个式子。即
$$ab\%p=[(a\%p)(b\%p)]\%p$$

有的人可能不太了解这个式子的由来，所以下面来推到以下这个式子。设$a=mp+i,b=np+j$,则有
$$\begin{array}{rl}ab\%p& =[(mp+i)(np+j)]\%p\\ & =[mn{p}^2+(niy+mjx)p+ij]\%p\\ & =ij\%p\end{array}$$
又因为$a\%p=i,b\%p=j$，所以可得
$$ab\%p=[(a\%p)(b\%p)]\%p=ij\%p$$

接下来看一下快速幂的思想，快速幂的思想就是将指数不断缩小分离出去。假如我们需要求解式子$3^{23}$，接下里看看如何进行这些操作。会有以下的变换。
$$\begin{array}{rl}{3}^{23}& =1\times 3^{23}由于指数是奇数，所以分离出来一个底数因子3\\ & =(1\times 3)\times 3^{23-1}\\ & =3\times 3^{22}由于指数部分是偶数，所以底数平方，指数减半\\ & =3\times (3^2{)}^{\frac{22}{2}}\\ & =3\times 9^{11}由于指数部分是奇数，需要分离出来一个底数因子9\\ & =(3\times 9)\times 9^{11-1}\\ & =27\times 9^{10}同上偶数，指数减半，底数平方\\ & =27\times 81^5同上奇数，分离一个底数因子\\ & =2187\times 81^4\\ & =2187\times 6561^2\\ & =2187\times 43046721^1\\ & =94143178827\times 43046721^0\\ & =94143178827\end{array}$$
这大概就是一个快速幂的想法，就是不断的观察指数部分是否为奇数，如果是奇数就分离一个底数出去；否则是偶数则将底数进行平方操作，指数减半。看上述流程到0则结束操作。用C语言代码进行描述如下：

long long int fastpower(long a, long b)
{
    // 结果
    long long ans = 1;
    while(b != 0)
    {
        // 奇数，分离一个底数出来，指数减1
        if(b % 2 == 1) 
        {
            ans = (long long)ans * a;
            b -= 1;
        }
        // 偶数操作，底数平方，指数减半
        else 
        {
            a *= a;
            b /= 2;
        }
    }

    return ans;
}

由于对于偶数的时候b/2与b>>2也是等效的；判断奇数偶数的条件也可以改为b&1，若该值为1则表示为奇数，否则为偶数。所以上述代码可以改进为以下形式。

long long int fastpower(long a, long b)
{
    // 结果
    long long ans = 1;
    while(b)
    {
        // 奇数，分离一个底数出来，指数减1
        if(b & 1) 
        {
            ans = (long long)ans * a;
            b -= 1;
        }
        // 偶数操作，底数平方，指数减半
        else  
        {
            a *= a;
            b >>= 1;
        }
    }

    return ans;
}

但是思考一下，若b是奇数，则执行完下一步操作一定是偶数，则其实奇数和偶数同时操作的时候可以直接等效于b>>=1。所以代码可以改进为：

long long int fastpower(long a, long b)
{
    // 结果
    long long ans = 1;
    while(b)
    {
        // 奇数，需要单独操作一次
        if(b & 1)  ans = (long long)ans * a;
        // 偶数操作，若奇数则下一步一定是偶数操作
        a *= a;
        b >>= 1;
    }

    return ans;
}

但是由于常见的快速幂的结果往往是需要对某个数字进行取模，所以加上最后的参数。最开始的式子其实经过推广可以得到：
$$a_1{a}_2\cdots a_{n-1}{a}_n\%p=[(a_1\%p)(a_2\%p)...(a_{n-1}\%p)(a_n\%p)]\%p$$
而$a^b$实际上就是$b$个$a$相乘，即：
$$\begin{array}{rl}{a}^b\%p& =\begin{array}{c}(\underbrace{a\times a\times \cdots \times a\times a})\\ b\end{array}\%p\\ & =\begin{array}{c}[\underbrace{(a\%p)(a\%p)\cdots (a\%p)(a\%p)}]\\ b\end{array}\%p\end{array}$$

若加上系数则为：
$$\begin{array}{rl}k\times a^b\%p& =\begin{array}{cc}k\times (& \underbrace{a\times a\times \cdots \times a\times a})\\ & b\end{array}\%p\\ & =\begin{array}{cc}[(k\%p)& \underbrace{(a\%p)(a\%p)\cdots (a\%p)(a\%p)}]\\ & b\end{array}\%p\end{array}$$

而在程序中a *= a正好对应着后续的$b$个$a$，该行代码可以改为a = a * a % p。而ans = (long long)ans * a正好对应着加上系数的式子，因此可以改成为ans = (long long)ans * a % p。于是最终的快速幂代码如下：

long long int fastpower(long a, long b, long p)
{
    // 结果
    long long ans = 1;
    while(b)
    {
        // 奇数，需要单独操作一次
        if(b & 1)  ans = (long long)ans * a % p;
        // 偶数操作，若奇数则下一步一定是偶数操作
        a = a * a % p;
        b >>= 1;
    }

    return ans;
}