### 1xx55's blog

By 1xx55, history, 12 months ago,

The goal is to find $\sum^{X-1}_{i=0}A^{i}$ $mod$ $m$ , and a simple thought is that we can calculate $\frac{A^{X}-1}{A-1}$. But when we divide $A^{X}-1$ by $A-1$ then $mod$ $m$, problem occurs: when we calculate $A^{X}-1$ , it's already $mod$ $m$ ,and there's maybe no reverse to it.

To solve this problem , I use a simple method: store $A^i$ with two numbers : $k$ and $r$ ,satisfying

$A^i \equiv k(A-1)+r \pmod {m(A-1)}$ , $0 \leq r \le A-1$

When we calculate $A^{x}$,we refresh $k$ and $r$ by multiplication ,then refresh $k$ by modulo $m$ , and refresh $r$ when $r \ge A-1$ : we do $k$ $+=$ $r/(A-1)$ and $r$ $=$ $r$ % $(A-1)$ ,like a carry.

We can prove that $r=1$ when $A \geq 2$ .But if $A=1$ , we can NOT use $k$ and $r$ to store this num for $A-1=0$ . But this case is easy to solve . The result is obviously $X \bmod m$ .

Since we get

$A^X \equiv k_{X}(A-1)+r_X \pmod {m(A-1)}$

we can get

$\frac{A^X-1}{A-1} \equiv k_{X} \pmod{m} (A \geq 2)$

So the answer is $k_{X}$ . Noted that this method is free to change the denominator(in this problem it's $A-1$).

Submission here: (GNU C11) Submission

If someone can help me why testcases AfterContest get WA?

• +4