快速幂
引题：现有两个整数m、n，求mnm^nmn除以1000000007之后的余数。
输入：输入整数m、n，用1个空格隔开，占1行。
输出：输出mnm^nmn除以1000000007之后的余数，占1行。
限制：1<=m<=1001<=m<=1001<=m<=100 ，1<=n<=1091<=n<=10^91<=n<=109
输入示例：5 8
输出实例：390625
1. 解决算法复杂度问题
如果用最直接的方法求xnx^nxn，我们需要进行n-1吃乘法运算，算法复杂度为O(n)。
不过，x的幂乘可以利用xn=(x2)n2x^n=(x^2)^\frac{n}{2}xn=(x2)2n的性质，用反复平方法快速求出。
该算法可以通过下面的递归函数实现：
pow(x,n)={1（n=0时）pow(x2,n/2)（n为偶数时）pow(x2,n/2)∗x（n为奇数时）pow(x,n)=\begin{cases}1&（n=0时）\\pow(x^2,n/2)&（n为偶数时）\\pow(x^2,n/2)*x&（n为奇数时）\end{cases}pow(x,n)=⎩⎪⎨⎪⎧1pow(x2,n/2)pow(x2,n/2)∗x（n=0时）（n为偶数时）（n为奇数时）
举个例子，3213^{21}321展开之后如下所示：
321=(3∗3)10∗3=910∗3=(9∗9)5∗3=815∗3=(81∗81)2∗81∗3=65612∗81∗3=(6561∗6561)1∗81∗33^{21}\\=(3*3)^{10}*3=9^{10}*3\\=(9*9)^5*3=81^5*3\\=(81*81)^2*81*3=6561^2*81*3\\=(6561*6561)^1*81*3321=(3∗3)10∗3=910∗3=(9∗9)5∗3=815∗3=(81∗81)2∗81∗3=65612∗81∗3=(6561∗6561)1∗81∗3
这样的话乘法运算的次数就从20次减少到了6次。只要算3 * 3，9 * 9，81 * 81，6561 * 6561以及多出的 *81和 *3，这六次乘法运算就可以。
似乎根据上面的分析我们可以得出代码：
int power(int a, int b)
{int ans = 1;while( b>0 ) {if( b&1 ) ans = ans*a; //当b为奇数时，乘以余下的一个ab >>= 1;//位运算，右移1位，相当于除以2a = a*a;}return ans;
}
这样，递归函数的参数n逐次减半，因此算法复杂度为O(logn)。
2. 解决取模运算问题
在遇到“求某计算结果除以M（本题中式1000000007）之后的余数”这类题时，可以按下述方法计算（这里a除以b之后的余数记作a%b）。
- 计算加法时，每相加一次执行一次%M
- 计算减法时，给被减数加上M之后，先算减法，后算%M
- 计算乘法时，每相乘一次执行一次%M
关于计算乘法时的公式：(a∗b)%M=(a%M)∗(b%M)(a*b)\%M=(a\%M)*(b\%M)(a∗b)%M=(a%M)∗(b%M)
证明：
设a除以M的余数和商分别为ar、aq，
b除以M的余数和商分别为br、bq，
即a/M=aq……ar，
b/M=bq……br，
则有：
a∗b=(aq∗M+ar)∗(bq∗M+br)=aq∗bq∗M2+ar∗bq∗M+aq∗br∗M+ar∗br=(aq∗bq∗M+ar∗bq+aq∗br)∗M+ar∗bra*b\\=(aq*M+ar)*(bq*M+br)\\=aq*bq*M^2+ar*bq*M+aq*br*M+ar*br\\=(aq*bq*M+ar*bq+aq*br)*M+ar*bra∗b=(aq∗M+ar)∗(bq∗M+br)=aq∗bq∗M2+ar∗bq∗M+aq∗br∗M+ar∗br=(aq∗bq∗M+ar∗bq+aq∗br)∗M+ar∗br
即易得：
(a∗b)%M=ar∗br=(a%M)∗(b%M)(a*b)\%M=ar*br=(a\%M)*(b\%M)(a∗b)%M=ar∗br=(a%M)∗(b%M)
类似可以得出：(a∗b)%M=[(a%M)∗(b%M)]%M(a*b)\%M=[(a\%M)*(b\%M)]\%M(a∗b)%M=[(a%M)∗(b%M)]%M
（引理1：积的取余等于取余的积的取余。）
公式：ab%M=(a%M)b%Ma^b\%M=(a\%M)^b\%Mab%M=(a%M)b%M
证明：
(a%M)b%M=[(a∗1)%M]b%M={[(a%M)∗(1%M)]%M}b%M=[(a%M)%M]b%M(a\%M)^b\%M\\= [(a*1)\%M]^b\%M\\=\{[(a\%M)*(1\%M)]\%M\}^b\%M\\=[(a\%M)\%M]^b\%M(a%M)b%M=[(a∗1)%M]b%M={[(a%M)∗(1%M)]%M}b%M=[(a%M)%M]b%M
由上面公式迭代：
[(a%M)b]%M=ab%M[(a\%M)^b]\%M=a^b\%M[(a%M)b]%M=ab%M
因此，解决了上述两个问题，我们就可以实现快速幂的算法代码了：
#include <iostream>
#define LL long long
using namespace std;
const LL mod=1e9+7;LL ksm(LL a,LL b)//快速幂
{LL ans = 1;a %= mod;while( b>0 ){if( b&1 ) ans = (ans*a)%mod;b >>= 1;//位运算，右移1位，相当于除以2a = (a*a)%mod;}return ans;
}
同理，易得快速乘的算法：
快速乘主要用于防止有两个较大的数相乘而直接乘爆, 因为是加法, 怎么都不可能加爆.，所以目的就是为了防止爆范围。
#include <iostream>
#define LL long long
using namespace std;
const LL mod=1e9+7;LL ksc(LL a,LL b)//快速乘，计算a*b%mod
{LL ans = 0;a %= mod;while( b>0 ){if( b&1 ) ans = (ans+a)%mod;b >>= 1;//位运算，右移1位，相当于除以2a = (a+a)%mod;}return ans;
}