快速幂顺带取余

正常求幂

PS:先不考虑异常输入， int溢出

int normalPow(int x, int n){
    int res = 1;
    while(n){
        res *= x;
        n --;
    }
    return res;
}

问题： n值小的时候计算量可以接受，一旦大了，计算量非常大，于是要将这个O(n)的算法优化。怎么优化？O(1)肯定不可能，所以往O(log(n))的方向考虑

快速幂

• 求 2^10. 循环10次每次2，等等，每次2，换成每次*4（2^{2）行不行？这样循环5次就完事了(10/2=5)。每次*8(2}3)行不行?可以，不过一个数除3余数的情况为0、1、2
• 由上一条可得：
  

long fastPow(long x, int power){
	long res = 1;
	while(power){
     	if(power&1) res = res * x;//如果奇数

     	x = x * x;//x-->x^2
     	power >>= 1;//除2，无论奇偶除2都一样，power是整数
	}
	return res;
}

快速幂带求余

• 这里涉及到了同余定理
• x^n % p = ((x^(n-1) % p) * (x % p)) % p,

快速幂顺带取余

原文：https://www.cnblogs.com/miyanyan/p/13804405.html