第 1 题
题意分析
给定三个整数 N,X,MN, X, MN,X,M，定义数列 AAA：
* A1=XA_1 = XA1 =X
* Ai+1=(Ai×Ai) mod MA_{i+1} = (A_i \times A_i) \bmod MAi+1 =(Ai ×Ai )modM，即前一项的平方再对 MMM 取模
要求计算前 NNN 项的和：∑i=1NAi\displaystyle \sum_{i=1}^{N} A_ii=1∑N Ai
关键约束：
* 1≤N≤10101 \le N \le 10^{10}1≤N≤1010（项数极大，不能逐项模拟到结束）
* 0≤X<M≤1050 \le X < M \le 10^50≤X<M≤105（值域非常小！）
由于 M≤105M \le 10^5M≤105，数列中的每一项取值范围都在 [0,M−1][0, M-1][0,M−1] 之间。根据鸽巢原理，最多经过 M+1M+1M+1 项就一定会出现重复值，从而进入循环节。一旦找到循环，我们就可以用 O(M)O(M)O(M) 的时间找到循环节，再用 O(1)O(1)O(1) 的时间计算剩余巨量的循环贡献。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路分析
核心思想：找循环节（周期）
因为值域有限，数列必然呈现 "非循环前缀 + 循环节" 的结构：
我们用数组记录：
1. seq[]：按顺序存储数列的每一项
2. pos[value]：记录每个值第一次出现时在 seq 中的下标（初始化 -1）
3. prefix[]：prefix[i] 表示 seq[0] 到 seq[i-1] 的累加和（即前 iii 项和），方便 O(1)O(1)O(1) 求区间和
模拟过程：
* 从 A1=XA_1 = XA1 =X 开始，逐个计算后续项
* 每遇到一个新值，记录其位置并入 seq
* 当某个值 current 已经被标记过位置 start = pos[current] 时，说明循环开始
* 当前已生成 idx 项：seq[0] ~ seq[idx-1]
* 而 current == seq[start]，意味着下一个要生成的项和历史上的第 start 项相同
* 循环节 = seq[start] ~ seq[idx-1]
* 循环长度 T = idx - start
* 循环节内元素和 = prefix[idx] - prefix[start]
求和时分三种情况：
1. N≤idxN \le idxN≤idx：还没走到（或刚好走到）循环点就结束了，直接用前缀和 prefix[N] 输出
2. N>idxN > idxN>idx：先加上前缀部分（seq[0] ~ seq[start-1]）的和，再计算后面还有多少个完整循环节和零散项
公式：
总和=prefix[start]+⌊N−startT⌋×cycle_sum+剩余零散项的和\text{总和} = \text{prefix}[start] + \left\lfloor \frac{N-start}{T} \right\rfloor \times \text{cycle\_sum} + \text{剩余零散项的和}总和=prefix[start]+⌊TN−start ⌋×cycle_sum+剩余零散项的和
复杂度
* 时间：O(M)O(M)O(M)，最多遍历值域大小 10510^5105
* 空间：O(M)O(M)O(M)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码实现（逐行解释）
