Compute S = (1 + a + a^2 + ... + a^(b-1)) mod m, the sum of a geometric series with b terms, where 0

Question

Compute S = (1 + a + a^2 + ... + a^(b-1)) mod m, the sum of a geometric series with b terms, where 0 <= a, 0 <= b <= 10^18, and 1 <= m <= 10^9. Use a divide-and-conquer recurrence so it runs in O(log b) modular operations (do NOT loop b times). If b == 0 the sum is 0.

Prep Room · Answer

### Intuition Summing a geometric series $\sum_{i=0}^{b-1} a^i pmod m$ sequentially would take $O(B)$ time, which is too slow if $B$ is up to $10^{18}$. To…

Geometric series modulo