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

àì夳堔傛蜴生んèń 2022-06-08 11:20 187阅读 0赞

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）：参考博客博主分析：  
![这里写图片描述][SouthEast]  
[参考博客地址——感谢博主][Link 1]

[vjudge题目链接][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;
    }

[SouthEast]: /images/20220608/a290ef879ec14f63a03c12b05d02e987.png
[Link 1]: http://blog.csdn.net/to_be_better/article/details/50658392
[vjudge]: https://vjudge.net/problem/CodeForces-55D