题目描述

难度分:$2500$

输入$T(\leq 10)$表示$T$组数据。

每组数据输入$L$，$R(1 \leq L \leq R \leq 9 \times 10^{18})$。

输出$[L,R]$内有多少个数字，能被其每个非零数位整除？

例如$240$能被$2$和$4$整除，符合要求。

输入样例$1$

1
1 9

输出样例$1$

9

输入样例$2$

1
12 15

输出样例$2$

12

算法

这个题感觉思路不算特别难，但是优化难度特别大，空间和时间都需要极大的优化才能过去。用灵佬第一版单考虑上界或下界的数位DP模板怎么都莽不过去，在$case11$就会超时；改成第二版同时考虑上下界模板才勉强通过。

数位DP

一边从高位到低位构造数字$num$，一边计算这个数字模上$2520$的余数$rem$，之所以要模上$2520$，是因为$lcm(1,2,3,4,5,6,7,8,9)=2520$。每考虑一个数位$d$，就按照公式$rem=(10 \times rem+d) \% 2520$更新$rem$，这样构造完最后一个数位后，得到的$rem$就是这个数除以$2520$的余数。而区间$[1,9]$中的整数组成非空子集，这些非空子集的最小公倍数有$48$种可能性。

对于某个数字$num$，如果它的非零数位集合为$S$，这个集合对应的最小公倍数为$j$。则只要构造完最后一个数位后满足$j|rem$（$|$为整除符号，$d|a$表示$a$能被$d$整除），就说明当前构造出来数字$num$是能被它所有非零数位整除的，因为$num$能够被$j$整除，那肯定能被计算出$j$的任何一个数字整除。

状态定义

$dp[i][j][rem][islimit][isnum]$表示当填到第$i$个数位（最高位从$0$开始）时，前面所有数位的最小公倍数为$j$，当前构造出来的数除以$2520$的余数为$rem$，前面的数位贴合上界情况为$islimit$，填数情况为$isnum$的情况下，从$1$到当前上界中的美丽数字个数。

在这个状态定义下，先求一遍$[1,R]$中的美丽数字个数$ub$，再求一遍$[1,L)$中的美丽数字个数$lb$，就能够得到答案为$ub-lb$。

状态转移

枚举当前数位能够填的数字$d$，使用灵茶山艾府的数位DP模板：

1. 先考虑当前数位不填的情况，当$isnum=0$时当前数位可以不填，状态转移方程为$dp[i][j][rem][islimit][isnum]=dp[i+1][j][rem][0][0]$。
2. 否则当前数位要填数，如果$isnum=0$，说明前面没有填过数字，当前位要从$1$这个下界开始枚举。上界要考虑$islimit=1$是否成立，如果成立，说明前面的数位贴合上界，当前数位的上界$ub$只能和上界的当前数位一样，否则可以为$9$。状态转移方程为$dp[i][j][rem][islimit][isnum]=\Sigma_{d=1-isnum}^{ub}dp[i + 1][lcm(j,d)][(10 \times rem+d)\% 2520][islimit=1 \land d=digit][1]$。

优化

空间优化

但是由于$1$到$9$所有非空子集的最小公倍数取值比较离散，如果直接存储数值会超空间，需要对这些最小公倍数进行离散化，将$0$到$2519$变成$0$到$47$。

时间优化

一方面，按照以上的思路，需要上界做一次数位DP，下界也做一次数位DP，常数比较大。因此，这里需要用数位DP模板$2.0$，同时考虑上下界，见下面的第二份代码。另一方面，不要在动规的过程中计算最小公倍数，而是先预处理出来。

复杂度分析

时间复杂度

状态数量为$O(48 \times 2520 \times A \times 2^2)$，其中$A$为最大数的数位个数，本题中为$19$。单次转移在最差情况下需要遍历数位的取值$[0,9]$，因此算法整体的时间复杂度为$O(10 \times 48 \times 2520 \times 2^2 \times A)$。

空间复杂度

空间瓶颈主要在于DP矩阵，离散化最小公倍数所开辟的空间对于它来说非常小。因此，算法的额外空间复杂度为$O(48 \times 2520 \times A \times 2^2)$。

C++ 代码

以上解法对应的是数位DP模板$1.0$的思路，代码如下，但是有大$case$会超时。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 48, M = 2520;
string s;
int n, t;
int lcms[N] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 18, 20, 21, 24, 28, 30, 35, 36, 40, 42, 45, 56, 60, 63, 70, 72, 84, 90, 105, 120, 126, 140, 168, 180, 210, 252, 280, 315, 360, 420, 504, 630, 840, 1260, 2520};
int lcmRes[N][10];
int idx[M + 1];
LL l, r, dp[20][N][M][2][2];

int lcm(int a, int b) {
    return (LL)a*b/__gcd(a, b);
}

void init() {
    for(int i = 0; i < N; i++) {
        idx[lcms[i]] = i;
    }
    for(int i = 0; i < N; i++) {
        lcmRes[i][0] = i;
        lcmRes[i][1] = i;
        for(int j = 2; j <= 9; j++) {
            lcmRes[i][j] = idx[lcm(lcms[i], j)];
        }
    }
}

LL dfs(int i, int j, int rem, int islimit, int isnum) {
    if(i == n) {
        return (isnum == 1 && rem % lcms[j] == 0)? 1: 0;
    }
    LL &v = dp[i][j][rem][islimit][isnum];
    if(v != -1) return v;
    LL cnt = isnum? 0: dfs(i + 1, j, 0, 0, isnum);
    int digit = s[i] - '0';
    int ub = islimit? digit: 9;
    for(int d = 1 - isnum; d <= ub; d++) {
        cnt += dfs(i + 1, lcmRes[j][d], (10*rem + d) % M, (islimit == 1 && d == digit)? 1: 0, 1);
    }
    return v = cnt;
}

int main() {
    scanf("%d", &t);
    init();
    while(t--) {
        scanf("%lld%lld", &l, &r);
        s = to_string(l - 1);
        n = s.size();
        for(int i = 0; i < n; i++) {
            memset(dp[i], -1, sizeof(dp[i]));
        }
        LL lb = dfs(0, 0, 0, 1, 0);
        s = to_string(r);
        n = s.size();
        for(int i = 0; i < n; i++) {
            memset(dp[i], -1, sizeof(dp[i]));
        }
        LL ub = dfs(0, 0, 0, 1, 0);
        printf("%lld\n", ub - lb);
    }
    return 0;
}

数位DP模板$2.0$的解法，同时考虑上下界的约束。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 48, M = 2520;
string high, low;
int n, t;
int lcms[N] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 18, 20, 21, 24, 28, 30, 35, 36, 40, 42, 45, 56, 60, 63, 70, 72, 84, 90, 105, 120, 126, 140, 168, 180, 210, 252, 280, 315, 360, 420, 504, 630, 840, 1260, 2520};
int lcmRes[N][10];
int idx[M + 1];
LL dp[20][N][M][2][2];

int lcm(int a, int b) {
    return a / __gcd(a, b) * b;
}

void init() {
    for(int i = 0; i < N; i++) {
        idx[lcms[i]] = i;
    }
    for(int i = 0; i < N; i++) {
        lcmRes[i][0] = i;
        lcmRes[i][1] = i;
        for(int j = 2; j <= 9; j++) {
            lcmRes[i][j] = idx[lcm(lcms[i], j)];
        }
    }
}

LL dfs(int i, int j, int rem, bool limitLow, bool limitHigh) {
    if(i == n) {
        return rem % lcms[j] == 0? 1: 0;
    }
    LL &v = dp[i][j][rem][limitLow][limitHigh];
    if(v != -1) return v;
    LL cnt = 0;
    int lo = limitLow? low[i] - '0': 0;
    int hi = limitHigh? high[i] - '0': 9;
    for(int d = lo; d <= hi; d++) {
        cnt += dfs(i + 1, lcmRes[j][d], (10*rem + d) % M, limitLow && d == lo, limitHigh && d == hi);
    }
    return v = cnt;
}

int main() {
    scanf("%d", &t);
    init();
    while(t--) {
        cin >> low >> high;
        n = high.size();
        low = string(n - low.size(), '0') + low;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < N; j++) {
                for(int k = 0; k < M; k++) {
                    dp[i][j][k][0][0] = dp[i][j][k][0][1] = dp[i][j][k][1][0] = dp[i][j][k][1][1] = -1;
                }
            }
        }
        printf("%lld\n", dfs(0, 0, 0, true, true));
    }
    return 0;
}