快速幂

  如何快速计算n^m?我们采用从特殊到一般的数学思想：

  假设n=2,m=10

  直接算的结果是2*2*2*2*...*2  计算了10次

  快速幂的思想是将m二进制化

  2¹⁰=4*16*16 计算了3次

  同理可得，n^m用快速幂来计算的过程是使底数不断倍增，指数倍减，达到时间上的优化：O(N)->O(logN)

  模板：

1 //读者可以根据自己的需要，更改返回值的类型 2 long long qpow(long long d){ 3     long long a=10,ans=1;//我们假设是求10^d 4     while(d>0){ 5         if(d&1)ans=(ans*a)%n;//当指数倍减至奇数时，和答案相乘 6         a=(a*a)%n;//底数倍增 7         d>>=1;//指数倍减 8     } 9     return ans;//返回答案10 }11 //根据二进制的拆分，时间复杂度是对数级别的