E - Geometric Progression Editorial by Yawn_Sean
Use Bases to Express the FormulaWe 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: