链接：

题意：

定义Beautiful number，这个数能整除自己的每位数字

题解：

数位dp，所不同的是需要多加一维，因为需要记录下当前的数字，

dp[i][j][k]表示枚举到i位，当前数字为j（这里的j是%2520之后的）,当前的最小公倍数为k

因为1-9的最小公倍数是2520,2520有48个因数，如果数组是ll dp[20][2520][2520]的话会超内存，所以对因子离散化一下就行了

代码：

31 ll a[20];32 ll dp[20][2550][50];33 int Hash[2550];34 35 ll gcd(ll a, ll b) {36     return b == 0 ? a : gcd(b, a % b);37 }38 39 ll lcm(ll a, ll b) {40     return a / gcd(a, b) * b;41 }42 43 ll dfs(int pos, int num, ll sta, bool limit) {44     if (pos == -1) return num%sta == 0;45     if (!limit && dp[pos][num][Hash[sta]] != -1) return dp[pos][num][Hash[sta]];46     int up = limit ? a[pos] : 9;47     ll res = 0;48     rep(i, 0, up + 1) {49         if (i == 0) res += dfs(pos - 1, (num * 10 + i) % 2520, sta, limit && i == a[pos]);50         else res += dfs(pos - 1, (num * 10 + i) % 2520, lcm(sta, i), limit && i == a[pos]);51     }52     if (!limit) dp[pos][num][Hash[sta]] = res;53     return res;54 }55 56 ll solve(ll x) {57     int pos = 0;58     while (x) {59         a[pos++] = x % 10;60         x /= 10;61     }62     return dfs(pos - 1, 0, 1, true);63 }64 65 int main() {66     int cnt = 0;67     rep(i, 1, 2521) if (2520 % i == 0) Hash[i] = cnt++;68     int T;69     cin >> T;70     memset(dp, -1, sizeof(dp));71     while (T--) {72         ll l, r;73         cin >> l >> r;74         cout << solve(r) - solve(l - 1) << endl;75     }76     return 0;77 }