初等数论是数学的一个分支，它既古老又现代。最早的数论研究是从素数开始的，2000多年前欧几里得就发现了算术基本定理，即每个正整数可以按递增顺序唯一地写成素数的乘积。现代数论的发展始于高斯，他发明了同余，使研究整除关系时与研究方程一样方便。把素数从合数中分出来是数论的一个关键问题，发展了很多素性检验法； 把正整数进行素因子分解是数论中的另一个核心问题； 寻求方程的整数解是又一个重要内容。
快速幂
对于幂运算an，如果一个个地乘，计算量为O(n)。如果用快速幂计算，只需计算O(logn)次。快速幂的一个解法是分治法，即先计算a2，再计算(a2) 2，…，一直计算到an。不过，标准的快速幂代码是利用位运算实现的。
下面以计算a11为例说明如何用倍增法计算快速幂。
(1) 幂次与二进制的关系。把a11分解为a11=a8+2+1=a8×a2× a1。其中，a1,a2,a4,a8…的幂次都是2的倍数，所有幂ai都是倍乘关系，可以逐级递推，在代码中用a*=a实现。
(2) 幂次用二进制分解。如何把11分解为8+2+1？利用数的二进制的特征，n=1110=10112=23+21+20=8+2+1，只需要把n按二进制处理就可以了。
(3) 如何跳过那些没有的幂次？例如，幂次为10112需要跳过a4。做一个判断即可，用二进制的位运算实现，即
n & 1，取n的最后一位，并且判断这一位是否需要跳过。
n >>= 1，把n右移一位，目的是把刚处理过的n的最后一位去掉。
int fastPow(int a, int n){ //计算anint ans = 1; //用ans返回结果while(n) { //把n看成二进制，逐个处理它的最后一位if(n & 1) ans *= a; //如果n的最后一位是1，表示这个地方需要乘a *= a; //递推：a2 --> a4 --> a8--> a16...n >>= 1; //n右移一位，把刚处理过的n的最后一位去掉}return ans;}
幂运算的结果往往是大数，一般先取模再输出。根据取模的性质anmod m=(a mod m)nmod m，把上述代码修改为
typedef long long ll; //变量改用较大的long longll fastPow(ll a, ll n, ll mod){ll ans = 1;a %= mod; //有一定作用，能在一定程度上防止下面的a*a越界while(n) {if(n & 1) ans = (ans*a) % mod; //取模a = (a*a) % mod; //取模n >>= 1;}return ans;}
上述代码也不是绝对完美的。第6行的ans*a可能超出long long范围，导致越界错误； 第7行的a*a也可能越界。虽然第4行的 a %=mod有一定预防越界的作用，但是做题时仍需谨慎，a不能太大。如果a很大，就只能用高精度处理大数了。
提示/
计算anmod m，如果n极大，例如n=1020000000，可以用“欧拉降幂”的数论方法，请自己查阅资料。
《算法竞赛》系列推文正在连载中，欢迎持续关注！
扫码优惠购书
