E - Geometric Progression Editorial by Yawn_Sean

Use Bases to Express the Formula

We are asked to calculate the sum of consecutive powers of \(a\), and in fact, such sums are closely related to one another.

We can calculate the sum of consecutive powers of \(a\) by calculating other series of sums. Take \(\sum\limits_{k=0}^{10} {a^k}\) as an example.

\(\sum\limits_{k=0}^{10} {a^k} = \sum\limits_{k=0}^{7} {a^k} + \sum\limits_{k=8}^{9} {a^k} +\sum\limits_{k=10}^{10} {a^k} = \sum\limits_{k=0}^{7} {a^k} +a^ 8 \sum\limits_{k=0}^{1} {a^k} +a^{10} \sum\limits_{k=0}^{0} {a^k} \)

By calculating the bases such as \(\sum\limits_{k=0}^{0} {a^k} , \sum\limits_{k=0}^{1} {a^k} , \sum\limits_{k=0}^{3} {a^k} , \sum\limits_{k=0}^{7} {a^k} ,...\) , we can express any sum of consecutive powers of \(a\) by using the binary expression of \(x\).

The time complexity is \(\mathcal{O}(\log x)\) or \(\mathcal{O}(\log^2 x)\), based on how you implement it .

Here is the code:

a, x, m = map(int, input().split()

orig = [1]
powers = [a % m]

while len(orig) < 40:
    orig.append(orig[-1] * (pow(a, 1 << (len(orig) - 1), m) + 1) % m)

while len(powers) < 40:
    powers.append(powers[-1] ** 2 % m)

ans = 0
times = 1
for j in range(39, -1, -1):
    if x >= 1 << j:
        ans += orig[j] * times % m
        ans %= m
        times *= powers[j]
        times %= m
        x -= 1 << j
print(ans)

posted:
last update: