Contest Duration: - (local time) (100 minutes) Back to Home

## E - Sequence Sum Editorial by evima

There are at most $$M$$ possible values of $$A_i$$. Therefore, the sequence starts to repeat at some point. Precalculate

• the number of terms before the cycle starts and their sum, and
• the number of terms in the cycle and their sum,

and calculate three values: the sum of elements before the cycle, the sum of repeating elements, and the sum of remaining elements; then the problem could be solved in a total of $$O(M)$$ time. Note that it may reach to the $$N$$-th element before entering the cycle.



Example: when $$M=449, A_1=2,N=1000$$

$$A=\{2,4,16,256,431,324,359,18,324,359,\ldots\}$$, and

• elements before the cycle: $$\{2,4,16,256,431\}$$
• elements in the cycle: $$\{324,359,18\}$$,

so the sum of first $$1000$$ elements can be calculated as $$(2+4+16+256+431) + (324+359+18)\times 331 + (324+359)$$.

posted:
last update: