快速幂概念

幂运算 aⁿ 即 n 个 a 相乘。快速幂就是高效地算出 aⁿ 。

快速幂算法实现

当 n 很大时，如 n = 10⁹ ，计算时间会很长，且结果会很大，常常超过变量类型的最大值。下面先考虑如何缩短计算时间，如果用暴力的方法直接算 aⁿ ，即逐个做乘法，时间复杂度是 O(n) ,即使能算出来，也会超时。

解决结果过大超过变量范围的问题需要用到高精度

暴力思想

逐个做乘法计算 aⁿ ,即计算 a×a×a×……a
代码非常容易理解，尽管这样可以计算n次幂，但是计算的时间太长，往往会超时

long long Pow(long long a,long long n) { long long ans(1); while(n--)         ans *= a; return ans; } 

暴力法时间复杂度为 O(n)

分治思想

对于 aⁿ 我们可以先算 a² , 然后再计算 (a²)² ,依次类推。也就是

当n为偶数时 ， 将 aⁿ 分解为 a^n/2 × a^n/2 , 再将 a^n/2 分解为 a^n/4 ……
当n为奇数时 ， 将 aⁿ 分解为 a^(n-1)/2+1 × a^(n-1)/2 , 然后依次类推 ……
这就是分治思想，将大问题分为几个小问题，算出小问题的答案，然后得出最终答案

long long fastPow(long long a,long long n) { if(n == 0) return 1; if(n == 1) return a; long long temp = fastPow(a,n/2); if(n%2 == 1) return temp * temp * a; else return temp * temp; } 

时间复杂度为 O(log₂n)

位运算思想

以a¹¹ 为例来说明位运算，a¹¹ = a⁸ ×a² ×a¹ , 不难看出2，8…都是2的倍数即a¹ ×a¹=a²
,a² × a² = a⁴ ，a⁴ × a⁴ = a⁸ ，产生的都是倍乘关系，逐级递推就可以。如何将11分解为8+2+1，这便利用了二进制，11的二进制为1011，即2³+2¹+2⁰, 也即8+2+1，这样就完成了分解。
下面的代码便是完成这样的操作：

long long fastPow(long long a,long long n) { long long base = a; long long res = 1; while(n){ if(n & 1)             res *= base;         base *= base;         n>>=1; } return res; } 

时间复杂度为 O(log₂n)

快速幂取模

由于幂运算的结果非常大，常常会超过变量类型的最大值，甚至超过内存所能存放的最大数，所以题目往往会要求对结果进行取模操作，缩小结果。

模运算公式

加 (a+b) mod m = ( (a mod m) + (b mod m) ) mod m
减 (a-b) mod m = ( (a mod m) – (b mod m) ) mod m
乘 (a×b) mod m = ( (a mod m) × (b mod m) ) mod m
然而，对除法进行类似 (a/b) mod m = ( (a mod m) / (b mod m) ) mod m 的操作是错误的，如(100/50) mod 20 = 2 , 而( (100 mod 20) / (50 mod 20) ) mod 20 = 0，两者并不相等，除法的取模需要用到逆元

显然由乘法的模运算公式可以推出 aⁿ mod m = (a mod m)ⁿ mod m
下面加上取模的算法都是依靠这个公式进行的

分治思想算法取模

long long fastPow(long long a,long long n,long long m) { if(n == 0) return 1%m; if(n == 1) return a%m; long long temp = fastPow(a,n/2,m); if(n%2 == 1) return (temp * temp * a)%m; else return (temp * temp)%m; } 

位运算思想算法取模

long long fastPow(long long a,long long n,long long m) { long long base = a; long long res = 1; while(n){ if(n & 1)             res = (res * base) % m;         base = (base * base) % m;         n>>=1; } return res % m; }