C++快速幂

前言

快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。

C++的实现方式：

先笔记一下：

b & 1  //取b二进制的最低位，判断和1是否相同，相同返回1，否则返回0，可用于判断奇偶（偶数二进制结尾是0奇数是1）
b>>1   //把b的二进制右移一位，即去掉其二进制位的最低位 就是b=b/2

递归的方式

long long  pow(long long a,long long b){
  if (b==0) return 1;
  long long temp=pow(a,b>>1);
  temp=temp*temp%MOD;
  if (b&1) temp=temp*a%MOD;
  return temp%MOD;
}

非递归的方式

long long power(long long a,long long b){
	long long t=1,y=a;
	while(b){
		if (b&1==1) t=t*y%k;
        y=y*y%k;
		b=b/2;
  }
  return t; 
}