← 返回题目列表

AtCoder · abc179_e

E. 序列和

中文机器翻译题面 查看原题

分数: 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