【题目来源】
洛谷：AT_abc466_f [ABC466F] Many Mod Calculation
【题目描述】
You are given integers \(N,X\) and a length-\(N\) sequence of positive integers \(A=(A_1,A_2,\ldots,A_N)\).
For a non-negative integer \(x\), define \(f(x)=(\ldots((x \bmod A_1) \bmod A_2) \ldots ) \bmod A_N\).
Find the number of integers \(x\) between \(1\) and \(X\), inclusive, such that \(f(x)=0\).
You are given \(T\) test cases; solve each of them.
给定整数 \(N, X\) 和一个长度为 \(N\) 的正整数序列 \(A=(A_1,A_2,\ldots,A_N)\)。
对于非负整数 \(x\)，定义 \(f(x)=(\ldots((x \bmod A_1) \bmod A_2) \ldots ) \bmod A_N\)。
求满足 \(1 \le x \le X\) 且 \(f(x)=0\) 的整数 \(x\) 的个数。
给定 \(T\) 组测试用例，请分别求解。
【输入】
The input is given from Standard Input in the following format:
\(T\)
\(\text{case}_1\)
\(\text{case}_2\)
\(\vdots\)
\(\text{case}_T\)
Each test case is given in the following format:
\(N\) \(X\)
\(A_1\) \(A_2\) \(\ldots\) \(A_N\)
【输出】
Output the answers for the test cases in order, separated by newlines.
【输入样例】
4
3 7
5 2 3
9 31415
9 9 8 2 4 4 3 5 3
1 1000000000000000000
1
9 20260405
3141 5926 5358 9793 2384 6264 3383 2795 288
【输出样例】
4
17452
1000000000000000000
77403
【核心思想】
-
问题分析：给定 \(N\) 个模数 \(A_1, A_2, \ldots, A_N\) 和查询上界 \(X\)，定义 \(f(x) = ((\ldots((x \bmod A_1) \bmod A_2) \ldots) \bmod A_N)\)，求 \([1, X]\) 内满足 \(f(x) = 0\) 的整数个数。这是一个数位 DP + 模数链优化问题，核心在于分析连续取模的性质——当 \(A_i \leq A_{i+1}\) 时，\(x \bmod A_i \bmod A_{i+1} = x \bmod A_i\)，因此只需保留严格递减的模数子序列。
-
算法选择：
- 前缀最小值压缩：构建严格递减序列 \(b\)，只保留对结果有实际影响的模数
- 递归/数位 DP：按递减模数分层，利用混合进制思想将 \([0, x]\) 分解为完整周期和余数部分递归计算
-
关键步骤：
- 模数压缩：遍历 \(A\)，仅当 \(A_i < b_{last}\) 时加入 \(b\)，得到严格递减序列 \(b_1 > b_2 > \ldots > b_m\)
- 预处理 \(g\)：\(g[i]\) 表示 \([0, b_i-1]\) 内满足 \(f(x) = 0\) 的数的个数，从右往左递推：
- \(g[m-1] = 1\)（只有 \(0\) 满足）
- \(g[i] = full \times g[i+1] + f(rem, i+2)\)，其中 \(full = \lfloor (b_i-1)/b_{i+1} \rfloor\)，\(rem = (b_i-1) \bmod b_{i+1}\)
- 查询函数 \(f(x, pos)\)：
- 找到第一个 \(\leq x\) 的模数 \(b_p\)（从位置 \(pos\) 开始）
- 若不存在：返回 \(x/b_m + 1\)
- 否则：\(x = q \times b_p + r\)，返回 \(q \times g[p] + f(r, p+1)\)
- 答案计算：\(f(X, 0) - 1\)（减去 \(x=0\) 的情况）
-
时间/空间复杂度：
- 时间复杂度：\(O(T \cdot (N + m^2))\)，预处理 \(O(N)\)，每次查询递归深度 \(O(m)\)
- 空间复杂度：\(O(m)\)，存储压缩后的模数序列和 \(g\) 数组
-
数位 DP 与模数链的核心思想：
- 模数冗余消除：若 \(A_i \leq A_{i+1}\)，则 \(x \bmod A_i < A_i \leq A_{i+1}\)，后续对 \(A_{i+1}\) 取模不改变结果。因此只需保留严格递减的模数，将 \(N\) 压缩为 \(m \leq \log(\max A)\) 量级
- 混合进制分解：将递减模数视为混合进制基数，\([0, x]\) 按 \(b_p\) 分解为 \(q\) 个完整周期和余数 \(r\)。每个完整周期 \([k \cdot b_p, (k+1) \cdot b_p - 1]\) 内的满足条件数相同，均为 \(g[p]\)
- 递归分层处理：余数部分 \(r < b_p\) 进入下一层模数处理，形成自然的递归结构
- 边界优化：当 \(x < b_{last}\) 时，\(f(x) = 0\) 当且仅当 \(x \bmod b_m = 0\)，即 \(x\) 是 \(b_m\) 的倍数，个数为 \(\lfloor x/b_m \rfloor + 1\)（包含 \(0\)）
- 适用于连续模运算、具有层次化周期结构的问题，核心是通过单调性压缩和周期性分解实现高效计数
【算法标签】
数位DP
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long longint n, X; // n: 序列长度; X: 查询上界
vector<int> b; // b: 递减的有效模数序列（前缀最小值）
vector<int> g; // g[i]: [0, b[i]-1] 内满足 f(x)=0 的数的个数
int m; // m: 有效模数个数// 数位DP核心：计算 [0, x] 内满足 f(x)=0 的数的个数
// pos：当前处理到第 pos 个模数
int f(int x, int pos)
{// 基准情况：超出模数范围，直接按最后一个模数计算if (pos >= m){return x / b.back() + 1;}// 找到第一个 <= x 的模数（从 pos 开始，使用 greater 实现降序 lower_bound）auto it = lower_bound(b.begin() + pos, b.end(), x, greater<int>());if (it == b.end()){// 所有模数都 > x，按最后一个模数计算return x / b.back() + 1;}int p = it - b.begin(); // p: 找到的模数在 b 中的位置// 混合进制分解：x = q * b[p] + rint q = x / b[p]; // q: 完整周期数int r = x % b[p]; // r: 余数// q 个完整周期 + 剩余部分递归处理return q * g[p] + f(r, p + 1);
}signed main()
{ios::sync_with_stdio(false); // 关闭同步，加速输入输出cin.tie(nullptr);int T; // T: 测试用例数量cin >> T;while (T--) // 循环处理每组测试用例{cin >> n >> X; // 读入序列长度和查询上界vector<int> a(n); // a: 原始模数序列for (int i = 0; i < n; i++)cin >> a[i];// 构建递减序列 b（前缀最小值）：只保留严格递减的模数b.clear();for (int i = 0; i < n; i++){if (b.empty() || a[i] < b.back()){b.push_back(a[i]);}}m = b.size(); // 有效模数个数// 预处理 g：从右往左递推g.resize(m);g[m - 1] = 1; // [0, b[m-1]-1] 内只有 0 满足 f(x)=0for (int i = m - 2; i >= 0; i--){// g[i] = [0, b[i]-1] 内满足条件的个数int full = (b[i] - 1) / b[i + 1]; // 完整 b[i+1] 周期数int rem = (b[i] - 1) % b[i + 1]; // 余数// 每个完整周期有 g[i+1] 个满足条件的数g[i] = full * g[i + 1];// 最后不完整部分 [0, rem] 递归计算// 从 i+2 层开始，因为 rem < b[i+1]，从 i+1 层取模不变g[i] += f(rem, i + 2);}// 答案：[1, X] 内满足条件的个数 = [0, X] - {0}int ans = f(X, 0) - 1;cout << ans << '\n';}return 0;
}
【运行结果】
4
3 7
5 2 3
9 31415
9 9 8 2 4 4 3 5 3
1 1000000000000000000
1
9 20260405
3141 5926 5358 9793 2384 6264 3383 2795 288
4
17452
1000000000000000000
77403