Build powers by repeated squaring
Reuse binary exponent contributions for logarithmic work.
Understand the idea
Maintain result, base, and exponent. For an odd exponent multiply result by base; then square base and halve exponent. The invariant is that result × base^exponent remains congruent to the original power. Initialize result with 1 % m.
Trace a small example
For 3^13 modulo 17, exponent bits select contributions for powers 8, 4, and 1, yielding 12. A recursive version must compute the half-power only once, otherwise it needlessly duplicates work.
#include <iostream>
// |a| <= 10^18, 0 <= e <= 10^18, 1 <= m <= 1000000007.
long long modPower(long long a, long long e, long long m) {
a %= m;
if (a < 0) a += m;
long long result = 1 % m;
while (e > 0) {
if (e % 2 == 1) result = result * a % m;
a = a * a % m;
e /= 2;
}
return result;
}
int main() { std::cout << modPower(3, 13, 17) << '\n'; }Conditions and cost
The iterative method uses O(log(e + 1)) time and O(1) space, and works for composite moduli too. In this complete example m ≤ 10^9 + 7 keeps products of reduced long long values safe. Modulus 1 and exponent 0 use the same initialization.
Prefix sum explorer
Query [l, r] is zero-based and inclusive. P[k] stores the total of the first k values; P[0] is zero.
Input array a
Prefix array P
Preprocess once in O(n). Each range sum then takes O(1).
Guided simulation · Change the inputs to test your understanding.
Why initialize with 1 % m instead of always 1?
Turn the idea into code
Compute 2^10 modulo 13.
Give me a hint
Use repeated squares, reducing after multiplication.
Show the explained solution
1024 mod 13 = 10. Binary power finds it with logarithmic work.
Your notes
Mark complete when you can explain it yourself.