分数: 500 点
问题陈述
让我们表示为 f(x, m) 欧几里得除法的余数 x by m.
让 A 是由初始值定义的序列 A_1=X 和递推关系 A_{n+1} = f(A_n^2, M)。 查找 \displaystyle{\sum_{i=1}^N A_i}.
约束
- 1 \leq N \leq 10^{10}
- 0 \leq X < M \leq 10^5
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N X M
输出
打印 \displaystyle{\sum_{i=1}^N A_i}.
示例输入 1
6 2 1001
示例输出 1
1369
序列 A 开始 2,4,16,256,471,620,\ldots 因此,答案是 2+4+16+256+471+620=1369.
示例输入 2
1000 2 16
示例输出 2
6
序列 A 开始 2,4,0,0,\ldots 因此,答案是 6.
示例输入 3
10000000000 10 99959
示例输出 3
492443256176507