A7078 | 函数求和
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
我们用函数 $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. $$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？