Introduce to Fast Power

Forx^n, write its power in binary formatn = \sum_{i = 0}^{k} = a_i2^i, and getx^n = \prod_{i = 0}^k x^{a_i2^i}

It is not difficult to get that when i + 1,x^{2^{i+1}} = (x^{2^{i}})^2, anda_i is an indicator, expressing the current binary i position.

That is, we can have a fast power algorithm:

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