Skip to main content

快速幂

对于 xnx^n 来说将其幂写成二进制格式n=i=0k=ai2in = \sum_{i = 0}^{k} = a_i2^i,得到xn=i=0kxai2ix^n = \prod_{i = 0}^k x^{a_i2^i} 不难得到在i + 1时,x2i+1=(x2i)2x^{2^{i+1}} = (x^{2^{i}})^2 ,而 aia_i 则是一个indicator,表达当前二进制i

res = 1
while (n){
if (n&1) res *= x; // res *= x^{1*2^i}
// n&0 => res *= x^{0*2^i} => res *= 1
x *= x; // x^{2^{i + 1}} = (x^{2^i})^2
}
return res