题意：有T组询问，每次询问区间[l, r]中的beautiful number有多少。beautiful number是指这个数可以被组成它的数字整除。例如15是beautiful number,因为15可以被1整除，也可以被5整除。25不是beautiful number, 25不能被2整除。
思路：很明显和数位有关，肯定是数位DP，然而题目中的这个条件不太好状态转移。题目中要求beautiful number可以被组成它的数字整除，也就是说它可以被组成它的数字的lcm整除。而1，2，......9的lcm是2520。那么我们把所有的数字对2520取模不会改变beautiful number的成立条件。因为1到9的数字的lcm是2520，那么1到9中的任意一些数的lcm（假设这个lcm数值为x）不会超过2520，并且x一定是2520的约数。所以，假设有一个数y%x == 0,那么y和x都取模2520之后等式仍然成立。这样状态数就大大减少了。设dp[i][j][k]为第i位，最高位到第i + 1位构成的数取模2520为j的数最高位到第i + 1位的数的lcm是k的方案数。这样假设我们询问1到x之间有多少个beautiful number可以用试填法来解决。我们需要枚举每一位填什么数来进行状态转移。假设数x的第i位是y，第i + 1位传进来了一个flag。flag是用来判断这一位可不可以填所有的数。如果可以，那么0到9都可以填。如果不可以，就只能填0 到 y。例如数字是123， 假设十位填的是1，那么个位填什么数都可以（flag此时是0）。假设10位是2，那么各位只能填0到3之间的数。通过枚举每一位填什么数来进行状态转移。
代码：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int mod = 2520;
LL dp[19][2525][50];
int mp[2525], re[20];
inline int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
inline int lcm (int a, int b) {
if(a == 0 || b == 0)return a + b;
return a * b / gcd(a, b);
}
LL dfs(int deep, int num, int now, bool flag) {
if(deep == 0) return (num % now == 0);
if(flag == 0 && dp[deep][num][mp[now]] != -1) return dp[deep][num][mp[now]];
LL ans = 0, end;
if(flag == 1) end = re[deep];
else end = 9;
for (int i = 0; i <= end; i++) {
ans += dfs(deep - 1, (num * 10 + i) % mod, lcm(now, i), flag & (i == end));
}
if(flag == 0) dp[deep][num][mp[now]] = ans;
return ans;
}
LL cal(LL num) {
int deep = 0;
while(num) {
re[++deep] = num % 10;
num /= 10;
}
return dfs(deep, 0, 1, 1);
}
int main() {
int cnt = 0, T;
for (int i = 1; i <= mod; i++) {
if(mod % i == 0) {
mp[i] = ++cnt;
}
}
memset(dp, -1, sizeof(dp));
scanf("%d", &T);
while(T--) {
LL a, b;
scanf("%lld%lld", &a, &b);
printf("%lld
", cal(b) - cal(a - 1));
}
}