Beautiful numbers - 题解
比赛与标签
比赛: Codeforces Beta Round 51 标签: dp, number theory 难度: *2500
题目大意喵~
主人，你好呀~ 这道题是关于一种叫做 "Beautiful numbers" 的特殊数字哦！一个正整数如果能被它自己的每一个非零数位整除，那它就是一个 Beautiful number 啦，是不是很奇妙的定义呢？(ฅ'ω'ฅ)
我们的任务就是，在给定的区间 [l, r] 中，找出所有 Beautiful number 的数量。因为 l 和 r 可能会非常非常大（最大到 9 * 10^18），所以直接一个一个数去检查肯定是不行的说。
这种在很大区间内计数的问题，通常都可以用 count(r) - count(l-1) 的方法来解决。也就是说，我们只需要实现一个函数 f(x)，它能计算出从 1 到 x 之间有多少个 Beautiful number，那么 [l, r] 区间的答案就是 f(r) - f(l-1) 啦！
解题思路大揭秘！
喵~ 既然是计数问题，而且和数字的每一位都有关系，那我们很快就能想到用 数位DP 来解决！数位DP就是一种按位来构建数字，并统计符合条件的数字个数的方法。
首先，我们来分析一下 "Beautiful number" 的性质：一个数 N 要被它所有的非零数位 d1, d2, ... 整除。这等价于，N 必须能被这些非零数位的最小公倍数 (LCM) 整除，对吧？
那么，在数位DP的过程中，我们需要记录哪些状态呢？
pos: 当前正在处理第几位数字。tight: 一个布尔标记，表示我们当前的选择是否受到上限数字x的约束。比如x = 845，我们填百位时，如果填了小于8的数字，那么十位和个位就可以随便填0-9；但如果百位填了8，那么十位就只能填0-4，这就是tight状态啦。lcm: 到目前为止，我们选择的所有非零数字的最小公倍数。rem: 到目前为止，我们构建出的数字本身。
但是，lcm 和 rem 的值可能会变得很大，直接作为DP状态的维度是不行的！怎么办呢？
关键突破口来啦！(๑•̀ㅂ•́)و✧
关于
lcm: 我们用到的数位只有 1 到 9。它们的最小公倍数LCM(1, 2, 3, 4, 5, 6, 7, 8, 9)是多少呢？算一下就会发现，它等于2520！这意味着，无论我们选择哪些非零数字，它们的lcm一定是2520的一个约数。而2520的约数只有 48 个！哇，状态一下子就从无限多变成了 48 个，这完全可以接受！我们可以预处理出这 48 个约数，并用它们的下标作为DP状态。关于
rem: 我们需要判断最终构成的数字N能否被lcm整除，即N % lcm == 0。因为我们知道lcm总是2520的约数，所以如果一个数N能被lcm整除，那么(N % 2520)也一定能被lcm整除。所以，我们不需要记录完整的数字N，只需要记录N % 2520的值就足够了！这个余数的状态也只有2520种。
所以，我们的DP状态就优化成了这样： dp(pos, lcm_idx, rem_mod_2520, tight, started)
pos: 当前处理的位数。lcm_idx: 当前lcm在48个约数中的索引。rem_mod_2520: 当前数字模2520的余数。tight: 是否受上限约束。started: 是否已经填入了非零数字（用来处理前导零的情况）。
这样，一个看似复杂的问题就被我们分解成 manageable 的小部分了呢！接下来只要按照数位DP的模板，从高位向低位递推填数，并转移状态就可以啦。
代码实现详解喵~
这份AC代码用的是迭代式的数位DP，思路和上面分析的是一样的哦，让本猫娘来给你详细解释一下吧~
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
// 求最大公约数，用来算最小公倍数 (lcm(a,b) = a*b/gcd(a,b))
ll gcd(ll a, ll b) {
if (b == 0) return a;
return gcd(b, a % b);
}
vector<int> divisors; // 存储2520的所有约数 (共48个)
int index_map[2521]; // 将约数值映射到它在divisors数组里的下标
int next_index[48][10]; // 预处理的状态转移表 next_index[当前lcm下标][新数字] = 新lcm下标
// 预处理的小魔法~ 提前算好所有需要用到的东西
void precompute() {
divisors.clear();
// 找到2520的所有约数
for (int i = 1; i <= 2520; i++) {
if (2520 % i == 0) {
divisors.push_back(i);
}
}
int total_divisors = divisors.size(); // 刚好是48个
memset(index_map, -1, sizeof(index_map));
// 建立约数值到下标的映射
for (int i = 0; i < total_divisors; i++) {
index_map[divisors[i]] = i;
}
// 预处理lcm状态的转移
for (int i = 0; i < total_divisors; i++) { // i是当前lcm的下标
for (int d = 0; d <= 9; d++) { // d是新加入的数字
if (d == 0) {
// 新数字是0，lcm不变
next_index[i][d] = i;
} else {
// 新数字非0，更新lcm
int current_lcm = divisors[i];
int g = gcd(current_lcm, d);
ll new_lcm = (ll)current_lcm * d / g;
// 注意，我们的状态里只存2520的约数，但中间计算的lcm可能超过2520
// 不过没关系，因为最终所有lcm都是2520的约数，所以可以直接用2520的约数来找它的下标
// 这里代码的逻辑是如果lcm超过2520，就用2520本身。实际上lcm(divisors[i], d) 不会超过2520
// 这是一个保守但正确的写法
next_index[i][d] = index_map[new_lcm];
}
}
}
}
// 计算[1, x]中Beautiful number的数量
ll f(ll x) {
if (x == 0) return 0;
string s = to_string(x);
int n = s.size();
// dp[tight][started][lcm_idx][rem]
// 用两层dp数组来滚动，节省一维空间
ll dp[2][2][48][2520];
memset(dp, 0, sizeof(dp));
// 初始状态：在开始填数之前，我们处于tight状态，还没开始填非零数，
// lcm是1(下标为0)，余数是0。只有1种方式到达这个状态。
dp[1][0][0][0] = 1;
// 按位进行DP
for (int i = 0; i < n; i++) {
ll new_dp[2][2][48][2520];
memset(new_dp, 0, sizeof(new_dp));
// 遍历所有可能的状态
for (int tight = 0; tight < 2; tight++) {
for (int started = 0; started < 2; started++) {
for (int idx = 0; idx < 48; idx++) {
for (int rem = 0; rem < 2520; rem++) {
if (dp[tight][started][idx][rem] == 0) continue; // 如果这个状态不可达，就跳过
// 确定当前位能填的数字上限
int limit = tight ? (s[i] - '0') : 9;
for (int d = 0; d <= limit; d++) {
// 计算下一位的状态
int new_tight = tight && (d == limit);
int new_started = started || (d > 0);
int new_rem = (rem * 10 + d) % 2520;
// 如果还没开始填非零数，lcm先保持为1(idx=0)
// 开始后，就用预处理的表来更新lcm的下标
int new_idx = new_started ? next_index[idx][d] : 0;
// 累加方案数
new_dp[new_tight][new_started][new_idx][new_rem] += dp[tight][started][idx][rem];
}
}
}
}
}
// 将新计算的dp状态复制回原数组，进行下一轮迭代
memcpy(dp, new_dp, sizeof(new_dp));
}
// DP结束后，统计所有符合最终条件的方案数
ll ans = 0;
for (int tight = 0; tight < 2; tight++) {
for (int started = 0; started < 2; started++) {
for (int idx = 0; idx < 48; idx++) {
for (int rem = 0; rem < 2520; rem++) {
// 必须是填过非零数的(即正整数)，并且最终数字(的余数)能被lcm整除
if (started && (rem % divisors[idx] == 0)) {
ans += dp[tight][started][idx][rem];
}
}
}
}
}
return ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
precompute(); // 先进行预处理
int t;
cin >> t;
while (t--) {
ll li, ri;
cin >> li >> ri;
// 区间[l, r]的答案 = count(r) - count(l-1)
ll ans_right = f(ri);
ll ans_left = f(li - 1);
cout << ans_right - ans_left << endl;
}
return 0;
}复杂度分析的说
- 时间复杂度: O(T * |S| * 2 * 2 * 48 * 2520 * 10) 的说。这里的
T是测试用例数，|S|是数字x的位数（最大约19）。虽然理论上界看起来很大，但实际上很多DP状态是不可达的，所以实际运行速度会快很多，完全可以通过！预处理的复杂度很小，可以忽略不计。 - 空间复杂度: O(2 * 2 * 48 * 2520) 的说。我们用滚动数组优化掉了一维
pos，所以空间主要由DP数组决定，即 O(|tight| * |started| * |lcm_states| * 2520)，大约是4 * 48 * 2520 * 8字节，在内存限制内是没问题的。
知识点与总结喵~
这道题真是一道非常经典的数位DP题，融合了数论的智慧，做完之后是不是感觉收获满满呀？(ɔˆ ³(ˆ⌣ˆc)
我们来总结一下学到的东西吧：
- 数位DP (Digit DP): 解决在超大数字区间内，统计满足特定性质的数字个数问题的强大武器。核心思想是按位构造，并记录必要的状态。
- 最小公倍数 (LCM) 性质: 本题的灵魂！通过发现所有非零数位的
lcm都是LCM(1..9) = 2520的约数，成功地把一个无限的状态空间压缩到了有限的48个。这是数论和DP结合的典范！ - 同余理论: 另一个关键点！要判断
N % lcm == 0，由于lcm是2520的约数，我们只需要知道N % 2520的值即可。这大大减小了需要记录的状态。 - 状态压缩与预处理: 将
lcm值映射到下标，并预处理状态转移表，是优化DP效率的常用技巧。
希望这篇题解能帮助到你哦！数位DP可能一开始会觉得有点绕，但多做几道题，理解了它的模式之后，就会觉得它其实很可爱啦！加油，主人！喵~