学步园

要你求在A到B区间内的所有beautiful数，beautifil数的定义是这个数能被它自身数位上的所有数整除。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define LL __int64
int id, mp[2555];
LL dp[22][55][2525];
int a[22];
int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}
int LCM(int a, int b) {
    return a*b/gcd(a, b);
}
LL dfs(int len, int lcm, int mod, bool lim) {
    if(!len) return mod%lcm == 0;
    if(!lim && ~dp[len][mp[lcm]][mod]) return dp[len][mp[lcm]][mod];
    int m = lim ? a[len-1] : 9;
    LL ret = 0;
    int i;
    for(i = 0; i <= m; i++) 
        ret += dfs(len-1, i ? LCM(lcm, i) : lcm, (mod*10+i)%2520, lim&&i==m);
    if(!lim) dp[len][mp[lcm]][mod] = ret;
    return ret;
}
LL gao(LL n) {
    int len = 0;
    while(n) {a[len++] = n%10; n/=10; }
    return dfs(len, 1, 0, 1);
}
int main() {
    int i, cas;
    for(i = 1; i <= 2520; i++) if(2520 % i== 0) mp[i] = ++id; // 处理出所有的最小公倍数，注意这里保存的有些数不是最小公倍数，但所有的最小公倍数都有映射。
    cin >> cas;
    LL l, r;
    memset(dp, -1, sizeof(dp));
    while(cas--) {
        cin >> l >> r;
        cout << gao(r) - gao(l-1) << endl;
    }
    return 0;
}