题意:定义"beautiful number"为一个数n能整除所有数位上非0的数字
分析:即n是数位所有数字的最小公倍数的倍数。LCM（1到9）=2520。n满足是2520的约数的倍数。dp[len][val][lcm]一维为数的位数，一维为%2520的值（保存原数不可能，也没必要，2520是可行的最小公倍数最大的一个），一维为当前数位的lcm，判断满足的条件是val%lcm==0。这题离散化2520的约数，否则空间开不下。
#include <bits/stdc++.h> typedef long long ll;
ll dp[20][2520][50];
int digit[20];
int id[2521];
int tot; int GCD(int a, int b) {
return b ? GCD (b, a % b) : a;
}
int LCM(int a, int b) {
return a / GCD (a, b) * b;
} void init_LCM() {
tot = 0;
for (int i=1; i<=2520; ++i) {
if (2520 % i == 0) {
id[i] = ++tot;
}
}
} ll DFS(int pos, int val, int lcm, bool limit) {
if (pos == -1) {
return val % lcm == 0;
}
ll &now = dp[pos][val][id[lcm]];
if (!limit && now != -1) {
return now;
}
int d = limit ? digit[pos] : 9;
ll ret = 0;
for (int i=0; i<=d; ++i) {
int tval = (val * 10 + i) % 2520;
int tlcm = i ? lcm / GCD (lcm, i) * i : lcm;
ret += DFS (pos - 1, tval, tlcm, limit && i == d);
}
if (!limit) {
now = ret;
}
return ret;
} ll solve(ll x) {
int len = 0;
if (x == 0) {
digit[len++] = 0;
} else {
while (x) {
digit[len++] = x % 10;
x /= 10;
}
}
return DFS (len - 1, 0, 1, true);
} int main() {
init_LCM ();
memset (dp, -1, sizeof (dp));
int T; scanf ("%d", &T);
while (T--) {
ll l, r; std::cin >> l >> r;
std::cout << solve (r) - solve (l - 1) << '\n';
}
return 0;
}