快速幂及其取余快速幂快速幂取余
快速幂快速幂的作用:快速计算底数的n次幂。 时间复杂度为:O(log₂N) (朴素方法为O(N) 原理以下以求a的b次方来介绍 把b转换成二进制数 该二进制数第i位的权为2i−12i−12^{i-1} 例: a11=a20+21+23a11=a20+21+23a^{11} = a^{2^0+2^1+2^3} 11的二进制是1011 11=23×1+22×0+21×...