How to speed up the process of exponentiation? Since we feel that dividing the power operation into n steps is too slow, we must find a way to reduce the steps and combine some parts into one step.
For example, if n can be 2 Divisible, then we can calculate half first and get a^\frac n 2 value, and then square this value to get the result. Although there is optimization in this way, the degree of optimization is very small and the complexity is still linear.
For another example, if we can find 2^k=n , then we can optimize the original operation into a^1,a^2,a^4,a^8... only need to k It can be completed in one operation and the efficiency is greatly improved. Unfortunately, this condition is obviously too harsh and has a very small scope of application. But this gives us an idea, although it is difficult for us to find 2^k=n but we can find 2^{k_1}+2^{k_2}+2^{k_3}+......+2^{k_m}=n . In this way, we can find the value of each item in a very short time through recursion.
We have all studied the conversion between base and base, and we know a b The value of a base number can be expressed as the sum of the product of the value of each digit and the weight. for example, 2 base number 1001 , its value can be expressed as 10 hexadecimal 1×2^3+0×2^2+0×2^1+1×2^0 , which is 9 . This perfectly meets the above requirements. able to pass 2 Come on n Converted to 2^{k_m} The sum of the sequences of 2 base number i bits (counting from the right, values are 1 or ), the corresponding 2^{i−1} exists in the sequence. for example, 13 for binary 1101 , he can be expressed as 2^3+2^2+2^0 , where since the second bit is, 2^1 The item is dropped.
In this case, we only need to calculate a^1、a^2、a^4、a^8... a^{2^{k_m}} The value of (the items in this sequence may not all exist, by n binary determination) and multiply them to complete the entire exponentiation operation. This algorithm can be easily implemented with the help of bit operations, and its complexity is \Omicron(\log n) .
long long qpow(long long a, long long n, long long mod) {
long long res = 1;
a %= mod;
while (n) {
if (n & 1) res = (res * a) % mod;
a = (a * a) % mod;
n >>= 1;
}
return res % mod;
}