Geometric Series Sum Mod

Problem

Return the sum a + a*r + ... + a*r^(n-1) modulo m without iterating n times.

Use the divide-and-conquer identity S(2k) = S(k) * (1 + r^k) with fast modular exponentiation, pulling out one term for odd counts. Return 0 when m is 1 or n is 0.

Hint

The even-length half can be built from the first half multiplied by one plus r to the half power.

Test cases

case 1

in: [1,2,4,1000]

expected: 15

case 2

in: [2,3,3,100]

expected: 26

case 3

in: [5,1,4,7]

expected: 6

case 4

in: [1,10,5,7]

expected: 2

case 5

in: [0,5,10,13]

expected: 0

case 6

in: [1,2,0,10]

expected: 0

Starter codePython

def geometric_series_mod(a, r, n, m):
    # Your code here
    pass

6 test cases · run your code against them in the editor