快速幂取模（快速的求一个幂式的模(余)，通常是大数取余的运算
1.模运算：
(a+b)%m=（a%m+b%m）%m
(a-b)%m=（a%m-b%m）%m
(a*b)%m=（a%m*b%m）%m
2.位运算：
& 按位与 >> 右移，正数高位补0，负数由计算机决定
按位与运算
按位与运算符"&"是双目运算符。其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位均为1时，结果位才为1，否则为0。参与运算的数以补码方式出现。 例如：9&5可写算式如下： 00001001 (9的二进制补码) &00000101 (5的二进制补码) 00000001 (1的二进制补码) 可见9&5=1。 按位与运算通常用来对某些位清0或保留某些位。例如把a 的高八位清 0 ，保留低八位，可作a&255运算（255 的二进制数为0000000011111111）。
右移运算符“>>”是双目运算符。其功能是把“>>”左边的运算数的各二进位全部右移若干位，“>>”右边的数指定移动的位数。例如： 设 a=15， a>>2 表示把000001111右移为00000011(十进制3)。 注意：对于有符号数，在右移时，符号位将随同移动。当为正数时，最高位补0，而为负数时，符号位为1，最高位是补0或是补1 取决于编译系统的规定。TurboC和很多系统规定为补
还可以判断奇偶x&1==0为偶，x&1==1为奇
（b>>=1）相当于 b/2
核心原理：（引用
对于任何一个整数的模幂运算
a^b%c
对于b我们可以拆成二进制的形式
b=b0+b1*2+b2*2^2+...+bn*2^n
这里我们的b0对应的是b二进制的第一位
那么我们的a^b运算就可以拆解成
a^b0*a^b1*2*...*a^(bn*2^n)
对于b来说，二进制位不是0就是1，那么对于bx为0的项我们的计算结果是1就不用考虑了，我们真正想要的其实是b的非0二进制位
那么假设除去了b的0的二进制位之后我们得到的式子是
a^(bx*2^x)*...*a(bn*2^n)
这里我们再应用我们一开始提到的公式，那么我们的a^b%c运算就可以转化为
(a^(bx*2^x)%c）*...*(a^(bn*2^n)%c)
这样的话，我们就很接近快速幂的本质了
(a^(bx*2^x)%c)*...*(a^(bn*2^n)%c)
我们会发现令
A1=(a^(bx*2^x)%c)
...
An=(a^(bn*2^n)%c)
这样的话，An始终是A(n-1)的平方倍（当然加进去了取模匀速那），依次递推
================================================
如：2^5=2^(0101)=2^(1+2^2)=(2^1)*(2^2)
5=0*2^3+1*2^2+0*2^1+1*2^0
===================================================
代码的实现
Int pow_mod(int a,int b,int c) { intans=1; //记录结果 a=a%c; //预处理，使得a处于c的数据范围之下 while(b) { if(b&1)ans=(ans*a)%c; //如果b的二进制位不是0，那么我们的结果是要参与运算的 b>>=1; //二进制的移位操作，相当于每次除以2，用二进制看，就是我们不断的遍历b的二进制位b/=2; a=(a*a)%c; //不断的加倍 累乘 幂的改变 } returnans; }注意 一般数很大，故：typedef long long ll;
一句话：因子取余相乘后再取余，余数不变。
