1xx55's blog

By 1xx55, history, 15 months ago, In English

Task-->ABC 293 E

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?

Full text and comments »

  • Vote: I like it
  • +4
  • Vote: I do not like it