快速幂取模
即快速求出（a^b)mod c 的值。由于当a、b的值非常大时直接求a^b可能造成溢出，并且效率低。
思路
原理就是基于(a*b \% c = ((a \% c)*(b \% c))\% c),(a^b \% c = (a \% c)^b \% c)公式。
求解快速幂：
设指数b用二进制表示为(b = (b_n b_{n-1}...b_2b_1b_0)_2)，
(b = b_0 + b_1*2^1 + b_2*2^2+...+b_{n-1}*2^{n-1} + b_n*2^n)，
(a^b = a^{b_0 + b_1*2^1 + b_2*2^2+...+b_{n-1}*2^{n-1} + b_n*2^n} = a^{b0}*a^{b_1*2^1}*a^{b_2*2^2} *...*a^{b_{n-1}*2^{n-1}} * a^{b_n*2^n})，
(a^b \% c = a^{b0}*a^{b_1*2^1}*a^{b_2*2^2} *...*a^{b_{n-1}*2^{n-1}} * a^{b_n*2^n} \% c)，
设(K_n = (a^{b_n*2^n})\%c)，求Kn的话，当bn=0时Kn=1，bn=1时(Kn=(a^{2^n})\%c)，因此再考虑计算((a^{2^n})\%c)。
((a^{2^n})\%c = [(a^{2^{n-1}}\%c)*(a^{2^{n-1}}\%c)]\%c)由此递推。
代码
python
def quick_powmod(a, b, c):
a = a % c
ans = 1 # 存放结果
while b != 0:
if b & 1: # 二进制与
ans = (ans * a) % c
a = (a * a) % c # 取模是防止溢出
b >>= 1 # 二进制向右移动一位
return ans
例如a=2 b=10 c=3，b的二进制表示为1010。
(2^{10} = 2^{0+ 1*2^1+0*2^2+1*2^3})，b的二进制位从右往左取，为0时，累乘a，为1时，将累乘结果乘到ans里。
快速乘取模
使用二进制将乘法转换为加法。
思路
与快速幂取模类似，将一个乘数转换为二进制计算。
例如(20*14 = 20*(1110)_2 = 20*2^0*0 + 20*2^1*1+20*2^2*1+20*2^3*1)
代码
Python
def quick_mulmod(a, b, c):
ans = 0
a = a % c
while b != 0:
if b & 1 :
ans = (ans + a) % c
a = (2*a) % c
b >>= 1
return ans
乍一看还是很不好懂的，举个例子推导一遍就明白了。