Sequence Sum

题目描述

令 $f(x, m)$ 表示 $x$ 被 $m$ 做欧几里得除法的余数。 令序列 $A$ 由初始值 $A_1=X$ 和递推关系 $A_{n+1} = f(A_n^2, M)$ 定义。 求 $\displaystyle{\sum_{i=1}^N A_i}$。

输入格式

标准输入的格式如下： $N$ $X$ $M$

输出格式

输出 $\displaystyle{\sum_{i=1}^N A_i}$。

6 2 1001

1369

1000 2 16

6

10000000000 10 99959

492443256176507

提示

$1 \leq N \leq 10^{10}$ 0 \leq X < M \leq 10^5 输入中的所有数值均为整数。序列 $A$ 开头为 $2,4,16,256,471,620,\ldots$ 因此答案为 $2+4+16+256+471+620=1369$.
序列 $A$ 开头为 $2,4,0,0,\ldots$ 因此答案为 $6$.

标签: AtCoder|abc179E

来源

AtCoder|abc179E