【数位DP+离散化】Beautiful numbers CodeForces

【数位DP+离散化】Beautiful numbers CodeForces - 55D

Think:
1知识点：数位DP(+记忆化搜索)+离散化
2题意：输入一个区间，询问在这个区间内有多少个beautiful number，a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits.
3题目分析：
（1）：由美丽的数字的定义可知，美丽数字为其每一位的lcm的倍数（2）：lcm(1,2,3,4,5,6,7,8,9) = 2520，9个数字任意组合的lcm可推知为lcm(1,2,3,4,5,6,7,8,9)的因子
（3）：当我们想要知道一个很大的数是否为一个new_lcm的倍数时，不需要存储这个很大的数，可以转而存储(这个很大的数)%lcm(1,2,3,4,5,6,7,8,9)
（4）：dp[数位][截止当前位的数对2520取模][截止当前位的数的lcm]
（5）：对于截止当前位的数的lcm可以通过离散化存储，否则直接存储的话三维数组dp[19+][2520+][2520+]会MLE，9个数字任意组合的gcd的数量为48个，因此离散化之后存储dp数组为dp[19+][2520+][48+]减少了使用的内存
（6）：参考博客博主分析：
这里写图片描述
参考博客地址——感谢博主

vjudge题目链接

以下为Accepted代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod = 2520;/*lcm(1, 2, 3, 4, 5, 6, 7, 8, 9) = 2520*/
int tp, link[24], hash[2520+14];
LL dp[24][2520+14][48+14];
LL gcd(LL a, LL b);
LL dfs(int pos, int num, int lcm, bool is_max);
LL solve(LL x);/*[0, x]*/
int main(){
    int T, cnt = 0;
    memset(hash, 0, sizeof(hash));
    for(int i = 1; i <= 2520; i++){
        if(2520%i == 0)
            hash[i] = cnt++;
    }
    ///printf("%d\n", cnt);/*cnt = 48*/
    memset(dp, -1, sizeof(dp));
    LL l, r;
    scanf("%d", &T);
    while(T--){
        scanf("%lld %lld", &l, &r);
        printf("%lld\n", solve(r)-solve(l-1));
    }
    return 0;
}
LL gcd(LL a, LL b){
    if(!b) return a;
    else return gcd(b, a%b);
}
LL solve(LL x){
    tp = 0;
    while(x){
        link[tp++] = x%10;
        x /= 10;
    }
    return dfs(tp-1, 0, 1, true);
}
LL dfs(int pos, int num, int lcm, bool is_max){
    if(pos == -1)
        return num%lcm == 0;
    if(!is_max && ~dp[pos][num][hash[lcm]])
        return dp[pos][num][hash[lcm]];
    int up_top = 9;
    if(is_max)
        up_top = link[pos];
    LL sum = 0;
    int new_num, new_lcm;
    for(int i = 0; i <= up_top; i++){
        i ? new_lcm = i/gcd(i, lcm)*lcm : new_lcm = lcm;
        new_num = (num*10+i)%mod;
        sum += dfs(pos-1, new_num, new_lcm, is_max && i == up_top);
    }
    if(!is_max)
        dp[pos][num][hash[lcm]] = sum;
    return sum;
}