（算法）快速幂运算和取模的基本知识

引子：在高精度中的麦森数中运用到了快速幂运算

求一个数的多少次方可以用到快速幂，原理a^11=a^1*a^3*a^8，而为什么是拆成1，3，8而不是其他的呢，是因为11转化为二进制码是1011，这就分别对应了他的权重，有了这个基本知识后，执行这种类似的运算就可以大幅度减少时间。实现这个代码还需要用到位运算&（比较每一位，相同才是1）和右移的基本知识（右移多少位就除2的多少次方），接下来看代码实现

int quick(int a, int b)//是求a的b次方
{
	int ans = 1, base = a;//ans为答案（ans为答案这个初始值肯定是1，base为a^(2^n)
	while(b > 0)//b会一直右移直到移完变成0
    {
		if(b & 1)//&是位运算，b&1表示b在二进制下最后一位是不是1，如果是：
			ans *= base;//把ans乘上对应的a^(2^n)
		
        base *= base;//base自乘，由a^(2^n)变成a^(2^(n+1))
		b >>= 1;//位运算，b右移一位，如101变成10（把最右边的1移掉了），10010变成1001。现在b在二进制下最后一位是刚刚的倒数第二位。结合上面b & 1食用更佳
	}
	return ans;
}

　　快速幂也会用到取模运算：

(A+B)modb=(Amodb+Bmodb)modb

(A×B)mod  b=((A mod b)×(B mod  b)) * modb