第 1 题

题意分析

给定三个整数 $N, X, M$，定义数列 $A$：

• $A_1 = X$
• $A_{i+1} = (A_i \times A_i) \bmod M$，即前一项的平方再对 $M$ 取模

要求计算前 $N$ 项的和：$\displaystyle \sum_{i=1}^{N} A_i$

关键约束：

• $1 \le N \le 10^{10}$（项数极大，不能逐项模拟到结束）
• $0 \le X < M \le 10^5$（值域非常小！）

由于 $M \le 10^5$，数列中的每一项取值范围都在 $[0, M-1]$ 之间。根据鸽巢原理，最多经过 $M+1$ 项就一定会出现重复值，从而进入循环节。一旦找到循环，我们就可以用 $O(M)$ 的时间找到循环节，再用 $O(1)$ 的时间计算剩余巨量的循环贡献。

---

思路分析

核心思想：找循环节（周期）

因为值域有限，数列必然呈现 "非循环前缀 + 循环节" 的结构：

A1, A2, ..., Ak, [Ak+1, ..., Ak+T], [Ak+1, ..., Ak+T], ...
^前缀部分^    ^^^^^^^^^^^一个循环节^^^^^^^^^^^^

我们用数组记录：

1. seq[]：按顺序存储数列的每一项
2. pos[value]：记录每个值第一次出现时在 seq 中的下标（初始化 -1）
3. prefix[]：prefix[i] 表示 seq[0] 到 seq[i-1] 的累加和（即前 $i$ 项和），方便 $O(1)$ 求区间和

模拟过程：

• 从 $A_1 = 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 \le idx$：还没走到（或刚好走到）循环点就结束了，直接用前缀和 prefix[N] 输出
2. $N > idx$：先加上前缀部分（seq[0] ~ seq[start-1]）的和，再计算后面还有多少个完整循环节和零散项

公式：

$\text{总和} = \text{prefix}[start] + \left\lfloor \frac{N-start}{T} \right\rfloor \times \text{cycle\_sum} + \text{剩余零散项的和}$

复杂度

• 时间：$O(M)$，最多遍历值域大小 $10^5$
• 空间：$O(M)$

---

代码实现（逐行解释）

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;   // N 最大 1e10，累加和可能极大，全部用 long long

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;          // 项数，最大 1e10，必须用 long long
    int X, M;      // 初值和模数，M <= 1e5 用 int 即可
    cin >> N >> X >> M;

    // ---------- 找循环节 ----------
    vector<ll> seq;                     // seq[i] 按顺序存储数列第 i+1 项的值
    vector<ll> prefix = {0};            // prefix[i] 表示 seq[0..i-1] 的累加和，prefix[0]=0
    vector<int> pos(M, -1);             // pos[v] 记录值 v 第一次在 seq 中出现的位置，-1 表示未出现

    ll cur = X;                         // 当前项 A_i，从 A_1 = X 开始
    int idx = 0;                        // 当前要填入 seq 的下标（也是已生成项数）

    while (pos[cur] == -1) {            // 当这个值还没出现过，继续模拟
        pos[cur] = idx;                 // 记录 cur 第一次出现的位置是 idx
        seq.push_back(cur);             // 把 cur 放入序列
        prefix.push_back(prefix.back() + cur);  // 更新前缀和：新前缀和 = 旧前缀和 + 当前值
        idx++;                          // 已生成项数 +1
        cur = (cur * cur) % M;          // 计算下一项：A_{i+1} = (A_i)^2 mod M
    }

    // 此时 cur 是一个已经出现过的值，循环找到了！
    int start = pos[cur];               // 循环节起始位置在 seq[start]
    int cycleLen = idx - start;         // 循环节长度 T
    ll cycleSum = prefix[idx] - prefix[start];  // 一个循环节内所有值的和

    // ---------- 分类计算答案 ----------
    ll ans = 0;

    if (N <= idx) {
        // 情况1：N 还没走到循环点就结束，直接取前 N 项前缀和
        ans = prefix[N];
    } else {
        // 情况2：N 超过了循环开始点
        // (1) 先加上前缀部分：seq[0] 到 seq[start-1] 的和
        ans = prefix[start];

        // (2) 剩下 N - start 项，都在循环节里反复走
        ll remain = N - start;          // 进入循环区后还剩多少项要算

        // 完整循环节的个数 × 每个循环节的和
        ans += (remain / cycleLen) * cycleSum;

        // (3) 最后可能还有不足一个循环节的零散部分
        ll rest = remain % cycleLen;    // 零散项数
        ans += prefix[start + rest] - prefix[start];  // 零散项的和（前缀和 O(1) 求区间）
    }

    cout << ans << '\n';
    return 0;
}