快速幂

题目描述

求$a$的$b$次方对$mod$取模的值

$1\leq a,b,mod\leq 10^9$

问题分析

每个正整数可以唯一表示为若干指数不重复的$2$的次幂的和。

$b$在二进制表示下有$K$位，其中第$i(0\leq i < k)$位的数字是$c_i$，那么：

$b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+\cdots+c_02^0$

因此：

$a^b=a^{c_{k-1}2^{k-1}}*a^{c_{k-2}2^{k-2}}*\cdots*a^{c_02^0}$

也就是说如果$b$的第$i$位$c_i$是$0$，那么$a^{c_{i}2^{i}}$就等于$a^0=1$；如果$c_i$是$1$，那么就等于$a^{2^i}$

又有$a^{2^i}=(a^{2^{i-1}})^2$，而$k=log_2(\lceil b+1\rceil)$（$\lceil\rceil$表示向上取整），故时间复杂度为$O(log_2b)$

所以每次取$b$中的$1$位($b\&1,b>>=1$)，每次$a$都平方($a=a*a\%mod$)，如果$b$的这一位是$1$就累积到$ans$中。