Binary exponentiation is a way to compute a^b mod (M) where a, b can be very large (on the order of 1e9). Iterating manually b times is too slow, so we must find a faster way. Note that if we know a^2, then we can get a^4 in 1 operation, then we can also get a^8 by squaring .. and so on. We can take advantage of this to get a^b in logB time by repeatedly splitting b in half, computing the result for those halves and then squaring it to find the actual answer.
| long long pow(long long a, long long b, long long MOD){ if(b == 0)return 1; if(b == 1)return a % MOD; long long half = pow(a, b / 2, MOD); half *= half; half %= MOD; if(b % 2 == 1){ half *= a; half %= MOD; //if b is odd, then we are missing a factor of a in our answer } return half; } |