核心逻辑与数学原理
标准的数位 DP（18.1 节）通常处理与“数字的具体形状、相邻差值、是否包含特定子串”等高度依赖十进制字面特征的计数问题。然而，NOIP 提高组及省选的高频考察方向，往往会将数位 DP 与代数数论（整除性、同余系、最大公约数）跨界融合。
当引入“整除”约束（例如：求一个数能否被它的各个数位之和整除，或者能否被一个固定的数 $M$ 整除）时，我们无法在数值完全组合出来后再去进行余数判定，因为那会退化为暴力枚举。我们必须利用同余的拓扑可加性与可乘性，将整除状态实时维护在数位向下推进的链条中。
1. 同余系统的数位状态机动态传导
设当前从高位到低位已经填好的前缀数字所代表的数值为 $X$。现在准备在当前位填入一个数字 $d$（$0 \le d \le 9$）。根据位置记数法的代数原理，新的前缀数值 $X'$ 将变为：
$$X' = X \cdot 10 + d$$
如果我们关心这个数对一个大质数 $M$ 的整除性，由于模运算（Modular Arithmetic）满足：
$$(X \cdot 10 + d) \bmod M = \left( (X \bmod M) \cdot 10 + d \right) \bmod M$$
这意味着，我们不需要在状态中记录宏观的数值 $X$，而只需要记录 $X \bmod M$ 的余数状态。这一步代数降维将无限的整数空间成功坍塌到了大小仅为 $M$ 的有限同余状态机中。
2. 动态模数系统的最小公倍数（LCM）坍塌
以经典神题“Hate Nineteen”（求区间内能被自身各个数位之和整除的数）为例。
- 核心矛盾：当前填数字时，我们压根不知道“最终的数位之和”是多少。如果不知道最终的模数是什么，我们就无法像上文那样维护一个固定的余数 $X \bmod M$。
- 代数化归：由于十进制下，一个 18 位的数字其最大的数位之和不超过 $9 \times 18 = 162$。这意味着最终的模数只可能在 $[1, 162]$ 之间。
- 数论降维：我们可以利用 最小公倍数（LCM） 的性质。令 $G = \text{lcm}(1, 2, 3, \dots, 162)$。根据同余的可约性：
$$X \equiv R \pmod G \implies X \equiv R \pmod m \quad (\forall m \le 162)$$
因此，我们只需要在搜寻过程中，统一维护数字 $X$ 对全局最大公倍数 $G$ 的余数即可。但在实战中，$1 \sim 162$ 的 LCM 是一个庞大天文数字。实际上，我们可以动态维护当前已经出现的数位之和的 LCM，或者直接将“当前余数”和“当前的数位之和”同时塞进状态维度中，利用记忆化进行极度稀疏的网格剪枝。
状态设计与算法推导
以经典数论数位 DP 问题为例：“求区间 $[L, R]$ 中有多少个数，满足其自身能被其各个非零数位的乘积整除”。
1. 状态空间定义
由于 $1 \sim 9$ 的所有数字的最小公倍数为 $\text{lcm}(1, 2, 3, 4, 5, 6, 7, 8, 9) = 2520$。任何非零数位乘积的质因子只可能包含 $2, 3, 5, 7$，因此最终的乘积必然能整除 $2520$。我们可以在搜寻时统一对 $MOD = 2520$ 取模。
设计 DFS 状态空间为：int dfs(int pos, int sum_mod, int current_lcm, bool lead, bool limit)
pos：当前数位。sum_mod：当前填好的前缀数字对 $2520$ 取模的余数。current_lcm：当前已经填过的所有非零数位的最小公倍数（LCM）。
2. 状态转移方程与同余推进
在当前位枚举填写数字 $i$：
- 新的余数：
next_mod = (sum_mod * 10 + i) % 2520 - 新的 LCM（若 $i \neq 0$）：
next_lcm = lcm(current_lcm, i)触底判定（pos < 0）：如果sum_mod % current_lcm == 0，说明该数字合法，返回 1，否则返回 0。
C++ 标准源码（NOIP/省选高难数论特化模板）
以下源码为“数位乘积整除性”的高效实现。为了防止 f 数组因第三维 current_lcm 达到 2520 而爆内存（MLE），代码引入了离散化映射算子。因为 $1 \sim 9$ 的组合 LCM 实际上只有 48 种可能，将 2520 维打散映射到 48 维，常数和空间可直接暴扣 50 倍。
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int BASE_MOD = 2520;
int digits[20];
int f[20][BASE_MOD][50]; // 优化：第三维使用离散化后的 LCM 编号（共48个）
int lcm_map[BASE_MOD + 5]; // 实际 LCM 到离散化编号的映射表
// 代数算子：求最大公约数
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
// 代数算子：求最小公倍数
int lcm(int a, int b) {
if (a == 0 || b == 0) return a + b;
return (a * b) / gcd(a, b);
}
// 预处理：离散化 2520 的所有因子，精简状态空间
void preprocess() {
int id = 0;
for (int i = 1; i <= BASE_MOD; ++i) {
if (BASE_MOD % i == 0) {
lcm_map[i] = id++;
}
}
}
// pos: 数位; sum_mod: 统一对2520取模的余数; curr_lcm: 当前非零位的最大公倍数
int dfs(int pos, int sum_mod, int curr_lcm, bool lead, bool limit) {
if (pos < 0) {
// 终局数论判定：全局余数能否整除数字各有效位的最小公倍数
return sum_mod % curr_lcm == 0 ? 1 : 0;
}
// 只有在无限制且脱离前导零时，才能使用复用因子编号
int lcm_id = lcm_map[curr_lcm];
if (!limit && !lead && f[pos][sum_mod][lcm_id] != -1) {
return f[pos][sum_mod][lcm_id];
}
int up = limit ? digits[pos] : 9;
int res = 0;
for (int i = 0; i <= up; ++i) {
int next_mod = (sum_mod * 10 + i) % BASE_MOD;
int next_lcm = (lead && i == 0) ? curr_lcm : lcm(curr_lcm, i);
res += dfs(pos - 1, next_mod, next_lcm, lead && (i == 0), limit && (i == up));
}
if (!limit && !lead) {
f[pos][sum_mod][lcm_id] = res;
}
return res;
}
long long solve(long long n) {
if (n <= 0) return 0;
int len = 0;
while (n > 0) {
digits[len++] = n % 10;
n /= 10;
}
// 初始 LCM 设为 1（乘法恒等元）
return dfs(len - 1, 0, 1, true, true);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
preprocess();
memset(f, -1, sizeof(f)); // 全局终身复用缓存
long long l, r;
if (cin >> l >> r) {
cout << solve(r) - solve(l - 1) << "\n";
}
return 0;
}
NOIP 实战避坑指南
1. 动态模数未做安全初始化（零模引发崩溃）
- 现象：在解决关于数位之和或乘积整除的问题时，若初始将
curr_lcm或sum_digits设为 0。当数字全是 0 触底时，代码执行sum_mod % curr_lcm，直接触发 Floating Point Exception（除以零异常），引发编译系统强制终止。 - 规避手段：在处理同余和公倍数时，初始状态必须赋予代数单位元（加法/数位和初始为
0，乘法/LCM 初始为1）。
2. 忽略模数顺延导致的拓扑状态错位
- 现象：在计算
next_mod时，错误地写成next_mod = sum_mod + i % BASE_MOD。这混淆了位置记数法的左移权值，直接摧毁了同余方程的正确性。 - 规避手段：牢记高位向低位推进的同余标准递推矩阵算子：
next_mod = (sum_mod * 10 + i) % MOD。
经典 NOIP/洛谷 真题
1. 洛谷 P4127 [AHOI2009] 同类分布
- 题意描述：给出两个正整数 $a$ 和 $b$，求区间 $[a, b]$ 内有多少个正整数满足：这个数能被它各个数位上的数字之和整除。$a, b \le 10^{18}$。
- 问题本质与解题思路：动态指定模数的同余数位 DP。
- 核心难点：模数（数位和）在搜索过程中动态改变，无法直接预处理出一个统一的全局大 LCM。
- 解决方案：由于 $10^{18}$ 的最大数位和为 $9 \times 18 = 162$。我们可以在外层直接强行枚举最终的数位之和究竟是多少（从 1 枚举到 162）。对于每一个指定的数位和 $M$，我们在内层跑一次标准的数位 DP。此时模数固定为 $M$，状态设计为
dfs(pos, rem, sum, limit)，其中rem为当前对 $M$ 的余数，sum为当前实际的数位和。当触底且sum == M且rem == 0时才确认为合法解。利用外层枚举化动态为静态，思想极其精妙。
2. 洛谷 P2657 [SCOI2009] windy 数
- 题意描述：不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。求区间 $[A, B]$ 内 windy 数的总数。$A, B \le 2 \times 10^9$。
- 问题本质与解题思路：邻域差值约束数位 DP。虽然不涉及高深数论，但它是检验前导零逻辑的标准基石题。
- 状态设计：
dfs(pos, pre, lead, limit)。其中pre记录上一位填写的数字。 - 核心细节：当前导零标志
lead = true时，说明当前位即使填写任何数字，都不会与上一位（实际上不存在的数字）发生差值冲突。因此，当lead = true且当前位填0时，继续向下传递lead = true，且pre码可以赋予任意安全值；只有当lead = false时，当前填写的数字 $i$ 必须严格满足abs(i - pre) >= 2。此题是全网数位 DP 选手的必经之路。