##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
(Computing large powers)
How do you compute 2^1000? You cannot multiply 2 by itself 1000 times. That is too slow and the result is enormous.
If the problem asks for the answer mod m, you can use fast exponentiation. This algorithm computes a^n mod m in O(log n) time by squaring.
The trick: a^n = (a^(n/2))^2 if n is even. If n is odd, a^n = a × a^(n-1).
