A7078. 函数求和
编程题
普及/提高-
知识点
题目描述
我们用函数 $f(x,m)$ 表示 $x$ 除以 $m$ 的余数（也就是 $x$ 对 $m$ 取模）。
给定三个整数 $N,X,M$，定义一个数列 $A$：
- 初始时有 $A_1 = X$；
- 对于每个整数 $i \ge 1$，有
$$ A_{i+1} = f(A_i^2, M). $$
请你计算
$$ \sum_{i=1}^N A_i $$
给定三个整数 $N,X,M$，定义一个数列 $A$：
- 初始时有 $A_1 = X$；
- 对于每个整数 $i \ge 1$，有
$$ A_{i+1} = f(A_i^2, M). $$
请你计算
$$ \sum_{i=1}^N A_i $$
输入格式
输入包含一行，包含三个整数 $N,X,M$。
输出格式
输出一个整数，表示
$$ \sum_{i=1}^N A_i $$
的值。
$$ \sum_{i=1}^N A_i $$
的值。
输入输出样例
输入 #1
6 2 1001
输出 #1
1369
输入 #2
1000 2 16
输出 #2
6
输入 #3
10000000000 10 99959
输出 #3
492443256176507
说明/提示
## 数据范围
- $1 \le N \le 10^{10}$；
- $0 \le X < M \le 10^5$；
- 输入中的所有数都是整数。
## 样例一：
数列 $A$ 为
$$ 2, 4, 16, 256, 471, 620, \dots $$
所以
$$ \sum_{i=1}^6 A_i = 2 + 4 + 16 + 256 + 471 + 620 = 1369. $$
## 样例二：
数列 $A$ 为
$$ 2, 4, 0, 0, 0, \dots $$
所以前 $1000$ 项之和为
$$ 2 + 4 + 0 + \dots + 0 = 6. $$
- $1 \le N \le 10^{10}$；
- $0 \le X < M \le 10^5$；
- 输入中的所有数都是整数。
## 样例一：
数列 $A$ 为
$$ 2, 4, 16, 256, 471, 620, \dots $$
所以
$$ \sum_{i=1}^6 A_i = 2 + 4 + 16 + 256 + 471 + 620 = 1369. $$
## 样例二：
数列 $A$ 为
$$ 2, 4, 0, 0, 0, \dots $$
所以前 $1000$ 项之和为
$$ 2 + 4 + 0 + \dots + 0 = 6. $$