Codeforces Beta Round 51 D. Beautiful numbers

D. Beautiful numbers

题意

定义一个正整数 $x$ 为 $beautiful$ 当且仅当：$x$ 能被其每一个数位（除了 $0$）整除

统计 $[l,r]$ 的 $beautiful$ 数的数量

思路

首先我们需要注意到的是：

如果一个数 $x$ 能被 $d_1、d_2...d_k$ 整除的话，那么 $x$ 一定能被它们的最小公倍数 $lcm(d_1,d_2,...,d_k)$ 整除。

证明的话非常简单，可以尝试用算术基本原理证明（把每一个 $d_i$ 拆分成若干个质数的乘积）

那么如果一个数有 $1$ ~ $9$ 所有数位都出现，那么它为 $beautiful$ 的前提就是它能被 $lcm(1,2,...,9)=2520$ 整除。对于其他的数位组合情况，可以发现它们的 $lcm$ 一定是 $2520$ 的一个因子。那么我们要处理的 $beautiful$ 数要关注的 $lcm$ 统计出来大概只有 $48$ 种。我们哈希一下就可以减少空间复杂度。

如果我们设计当前的 $DP$ 状态为：低 $pos$ 位为全变化位，其他高位已经确定的数位（$0$ 除外）的最小公倍数为 $lcm$，高位确定位构成的数字模除 $lcm$ 的余数为 $r$。即 $dp[pos][r][lcm]$ 限制下 $beautiful$ 数的数量。

可以发现 $lcm$ 是动态变化的，我们无法通过当前的 $lcm$ 确定最底层的 $lcm$ ，那么我们模除 $lcm$ 的 $r$ 就无法确定。这里有个小技巧：我们可以先模除 $2520$。这是因为所有的 $lcm$ 都是 $2520$ 的因子，假设 $x=k?2520+b$，那么 $x$ % $2520$ % l$cm=b$ % $lcm$，最终结果和直接模 $lcm$ 是一样的 （$2520$ 是 $lcm$ 的倍数）。

这样子我们就将 $r$ 限制为了 $[0,2520?1]$ 的数，对于当前枚举的数位是 $0$ 时，$lcm$ 直接传递即可，否则要传新的 $lcm$。

还有一个 $tips$ 就是：这里多个样例的情况，$dp$ 数组不用重置，只需要在程序开始时初始化即可。因为这里所有的搜索都是建立在同一种限制条件下的 ，前面样例搜过的结果可以直接用到后面的搜索上。

时间复杂度：$O(len\times 2520\times (2520的因子数))$

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3e;
const long long INFLL=1e18;

typedef long long ll;

ll dp[20][2550][60];
int num[20];
int hash[2550];
int cnt;

ll dfs(int pos, int r, int Lcm, bool limit){
    if(!pos) return r % Lcm == 0;
    if(!limit && ~dp[pos][r][hash[Lcm]]) return dp[pos][r][hash[Lcm]];
    ll res = 0;
    int up = (limit ? num[pos] : 9);
    fore(i, 0, up + 1){
        if(!i) res += dfs(pos - 1, r * 10 % 2520, Lcm, limit && i == up);
        else res += dfs(pos - 1, (r * 10 + i) % 2520, std::lcm(Lcm, i), limit && i == up);
    }
    if(!limit) dp[pos][r][hash[Lcm]] = res;
    return res;
}

ll solve(ll x){
    int len = 0;
    while(x){
        num[++len] = x % 10;
        x /= 10;
    }
    return dfs(len, 0, 1, true); //初始lcm为1
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    fore(i, 1, 2521)
        if(2520 % i == 0)
            hash[i] = ++cnt;
    int t;
    std::cin >> t;
    memset(dp, -1, sizeof(dp));
    while(t--){
        ll l, r;
        std::cin >> l >> r;
        std::cout << solve(r) - solve(l - 1) << endl;
    }
    return 0;
}