题目大意：对于一个数 $x$，定义 $f(x)$ 为 $x$ 的各个数位的乘积，对于 $L_1 \le x \le R_1$，问有多少 $x$ 满足 $L_2 \le f(x) \le R_2$？$0 \le L_1,R_1,L_2,R_2 \le 10^{18}$
首先，按照数字包含至少一个 $0$ 和完全不包含 $0$ 分别DP。
完全不包含 $0$：
由于 $f(x)$ 是由 $1 \cdots 9$ 乘起来的，那么对其进行质因数分解，质因数只可能是 $2,3,5,7$。
题目中的 $L_2,R_2$ 不超过 $10^{18}$，可以计算出 $2$ 最多为 $59$ 个，$3$ 最多为 $37$ 个，$5$ 最多为 $25$ 个，$7$ 最多 为 $21$ 个。
但这题的空间卡得很紧，如果去掉包含 $0$ 的情况，$2$ 最多为 $51$ 个，$3$ 最多为 $34$ 个，$5$ 最多为 $18$ 个，$7$ 最多为 $19$ 个。
DP做法：
设 $f[i][c2][c3][c5][c7][0/1][0/1]$ 表示前 $i$ 位数的乘积等于 $2^{c2}3^{c3}5^{c5}7^{c7}$ 的方案数，有状态转移方程：
其中 $d2,d3,d5,d7$ 表示第 $i$ 位的数是 $2^{d2}3^{d3}5^{d5}7^{d7}$，后两维表示卡不卡上界和卡不卡下界。
记搜做法：
记搜不仅快，而且还很好写。
设 $f[i][c2][c3][c5][c7]$ 表示前 $i-1$ 位数的乘积等于 $2^{c2}3^{c3}5^{c5}7^{c7}$，且不卡上界，为了达到目标状态，可以从第 $i$ 位开始添加多少种不同的数（注意 $f[i][c2][c3][c5][c7]$ 与前 $i-1$ 位数的种类无关）。
记搜时，我们需要记录两个参数 $prefix$ 和 $flag$ 分别表示前 $i$ 位是不是前导零和卡不卡上界，至于卡下界的情况，只需要用 $calc(r)-calc(l-1)$ 容斥一下，并且 $calc(l-1)$ 时不需要重新 $memset$，直接在 $calc(r)$ 的答案的基础上做就可以。
至少包含一个 $0$：
设 $g[i][0/1]$ 表示前 $i-1$ 位的乘积是否为 $0$，且不卡上界，为了达到目标状态，可以从第 $i$ 位开始添加多少种不同的数（还是与前 $i-1$ 位数的种类无关）。
记搜方法与上文相仿。
有一个需要注意的点，如果所有的位都是 $0$ 的话会被 $prefix$ 当做前导零来处理，不计入答案，因此 $calc$ 的时候需要在 $dfs2$ 的返回值上加一。
#include <cstdio>
#include <cstring>
typedef long long LL;
const int d2[10] = {0, 0, 1, 0, 2, 0, 1, 0, 3, 0};
const int d3[10] = {0, 0, 0, 1, 0, 0, 1, 0, 0, 2};
const int d5[10] = {0, 0, 0, 0, 0, 1, 0, 0, 0, 0};
const int d7[10] = {0, 0, 0, 0, 0, 0, 0, 1, 0, 0};
LL f[18][52][35][19][20], g[18][2], p2[52], p3[35], p5[19], p7[20], L1, R1, L2, R2; int a[18];
LL dfs1(int cur, int c2, int c3, int c5, int c7, bool prefix, bool flag) { //完全不包含0
if (cur < 0) return (p2[c2] * p3[c3] * p5[c5] * p7[c7] >= L2 && p2[c2] * p3[c3] * p5[c5] * p7[c7] <= R2) && !prefix;
LL &x = f[cur][c2][c3][c5][c7];
if (!flag && !prefix && ~x) return x;
int upper = flag ? a[cur] : 9; LL tmp = 0;
for (int i = prefix ? 0 : 1; i <= upper; ++i)
tmp += dfs1(cur - 1, c2 + d2[i], c3 + d3[i], c5 + d5[i], c7 + d7[i], prefix && i == 0, flag && i == upper);
if (!flag && !prefix) x = tmp;
return tmp;
}
LL dfs2(int cur, int val, bool prefix, bool flag) { //包含至少一个0
if (cur < 0) return !val;
LL &x = g[cur][val];
if (!flag && !prefix && ~x) return x;
int upper = flag ? a[cur] : 9; LL tmp = 0;
for (int i = 0; i <= upper; ++i)
tmp += dfs2(cur - 1, val && (prefix || i != 0), prefix && i == 0, flag && i == upper);
if (!flag && !prefix) x = tmp;
return tmp;
}
LL calc(LL x) {
if (x < 0) return 0;
int len = 0;
while (x) a[len++] = x % 10, x /= 10;
return dfs1(len - 1, 0, 0, 0, 0, 1, 1) + (L2 == 0 ? dfs2(len - 1, 1, 1, 1) + 1 : 0); //注意这里需要+1, 即数字0的情况
}
int main() {
scanf("%lld%lld%lld%lld", &L1, &R1, &L2, &R2);
p2[0] = p3[0] = p5[0] = p7[0] = 1;
for (int i = 1; i <= 51; ++i) p2[i] = p2[i-1] * 2;
for (int i = 1; i <= 34; ++i) p3[i] = p3[i-1] * 3;
for (int i = 1; i <= 18; ++i) p5[i] = p5[i-1] * 5;
for (int i = 1; i <= 19; ++i) p7[i] = p7[i-1] * 7;
memset(f, -1, sizeof f);
memset(g, -1, sizeof g);
printf("%lld\n", calc(R1) - calc(L1 - 1));
return 0;
}
时间复杂度 $O(?)$