[CF55D] Beautiful numbers题解

题目传送门

前置知识：数位DP、同余

题目大意：

在l到r中统计能被其所有非零数字整除的数的个数，多组询问，\(t \leq 10\)，\(1 \leq l \leq r \leq 9 \times 10^{18}\)

题目分析

注意力以及数学归纳发现没有规律可找

题目涉及对数字每一位的设计，查询为一个区间，数位之间有依赖性，于是考虑数位DP

每次dfs记录下当前的位置、上限、数字和，

关键转化：

• 如果数字是 \(x\)，它的各位数字是 \(d_1, d_2, …, d_n\)

• 要求：\(x \% d_1 == 0 \; \&\&\; x \% d_2 == 0 \;\&\&\; …\)

• 等价于：\(x \% lcm(d_1, d_2, …, d_n) == 0\)

此处省略数学证明，感兴趣可以上网自行查阅

因此我们再记录下当前所有数位（0除外）的最小公倍数（lcm）

那么问题来了，

最小公倍数我们还能稍微离散化一下，那这个数字和如何把他写进dp里面呢

众所周知\(dp[9000000000000000000]\)是一个一定会炸的东西

离散化？行不通啊

Part 1：怎样转化

观察到：

• 令sum为当前的数字

• sum在不断变化

• 上面那一条导致dp空间利用率很高（大白话：dp空间不怎么浪费）

• 所以只能想办法把这个sum转换一下

一条作者经验总结出来的废话：你想要优化一个东西，先得明白他最后产生了什么作用

发现sum最后产生的作用：搜索搜到头的时候判断当前这种方案是否合法，也就是判断sum%lcm==0

学过同余的同学都知道，我们此时可不可以找到一个数w使得\(sum \equiv w \pmod{lcm}\)

学过数学的同学都知道，这个w不可能凭空而来

同余学得稍微好一点的同学可以发现一个性质：\(a \% b ≡ a \% (k\times b) \pmod {b}\)

欸？假设上面的那个a就是我们的sum，那sum%b%b，不就等于sum%b，也就是我们最后判断的东西吗

相当于前面的那个%b我们可以去掉啊，式子就变成了\(a ≡ a \% (k\times b) \pmod {b}\)

于是乎，我们就找到了一个可以替代a（sum）的东西，也就是\(a\%(k\times b)\)，此处b就是我们的lcm

为了保证解的一致性和正确性，我们需要找到一个通用的\(k \times b\)，k为正整数

但是这个b（lcm）不是随着我们的递归在不断变化吗……

分析一下，b只由1-9这几个数字中选出若干个相乘而得

注意力观察一下可得：\(k \times b\)只要等于1-9这几个数的最小公倍数即可，也就是2520

回顾一下，我们前面的问题：这个数字和如何把他写进dp里面呢

答案就是每次把sum模2520

Part 2：炸飞作者的细节

• dp的初始化

  一般来说，dp的初始化是放在每次dfs之前，

  但是我们这里是非常不友好的多组数据

  发现：

  • dp 里存的状态是“与具体数字无关”的。

  • 也就是说，只要满足dp内的限制，当前状态就可以直接记忆化掉

  • 那么无论这个数是多少，情况相同的dp值总是相同的

  • 那我们就可以不用每次都清空dp了，不同组的数据也可以直接复用

  • 注意【WARNING】：作者平时习惯用step记录当前是第几位，但是此处需要记录的是还剩多少位，原因请结合dp的复用自行探究~

• lcm的处理

  • 1-9都只是个位数，很小，时间开销很小，请不要像作者一样脑子抽了自找麻烦做没啥用处预处理

  • 记得判0

  • 请留意你离散化之前之后的数据范围和数组大小……

• 数组的使用

  • 请不要像作者一样作死使用dp[20] [2530] [2530]这样的数组，作者已经教会了你如何优化

  • 请不要没算清楚范围就盲目开数组

Part 3：总结

此题的本质：

• 压缩判断条件：把“能被所有非零位整除”这个复杂的多条件判断，通过 LCM 等价转化为“能被一个数整除”的单条件判断。

• 压缩状态空间：因为 LCM 只有 48 种，而判断只需 \(x \% LCM\)，所以把无限大的数字 x压缩成 \(x \% 2520\)，把无限多种状态压缩成 20 × 48 × 2520 个可枚举状态。

在时间和空间当中找到一个平衡点

代码实现

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

typedef long long ll;
const int MAXN = 20;
int w[MAXN];
ll dp[MAXN][2530][50];
ll l, r;
ll d = 2520;
int idx = 0;
int id[2530];

int lcm(int x, int y) {
    if (x == 0) return y;
    return x * y / __gcd(x, y);
}

ll dfs(int step, bool lead, bool lim, int sum, int lc) {
    if (!step) { // 倒着来
        if (lead) return 0;
        return (sum % lc == 0);
    }
    int lid = id[lc];
    if (!lead && !lim && ~dp[step][sum][lid]) return dp[step][sum][lid];
    int up = lim ? w[idx - step + 1] : 9; // 注意细节
    ll tot = 0;
    for (int i = 0; i <= up; i++) {
        int new_lead = (lead && i == 0);
        tot += dfs(step - 1, new_lead, (lim && i == up), (sum * 10 + i) % d, lcm(i, lc));
    }
    if (!lead && !lim) return dp[step][sum][lid] = tot;
    return tot;
}

ll sol(ll x) {
    if (x <= 0) return 0;
    idx = 0;
    while (x) {
        w[++idx] = x % 10;
        x /= 10;
    }
    for (int i = 1; i <= idx / 2; i++) swap(w[i], w[idx - i + 1]);
    return dfs(idx, 1, 1, 0, 1);
}

void init() {
    memset(dp, -1, sizeof(dp)); // 初始化写在外面
    int p = 0;
    for (int i = 1; i <= 2520; i++) if (2520 % i == 0) id[i] = ++p;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    init();
    while (t--) {
        cin >> l >> r;
        cout << sol(r) - sol(l - 1) << endl;
    }
    return 0;
}

鸣谢：

Deepseek

Codeforces

友情出演：

Deepseek

The End

欢迎Debug！

原文链接：[CF55D] Beautiful numbers题解