CF55D Beautiful numbers

求 \([l,r]\) 中满足 \(x\) 能被 \(x\) 数位中所有非 \(0\) 位整除的数的个数。 \(l,r\leq 9\times10^{18}\) 。

---

\(lcm(1\sim9)=2520\) 。

标准的数位DP。用 \(dp[i][j][k]\) 表示统计到第 \(i\) 位，前 \(i\) 位数字 \(mod\,2520\) 的余数为 \(j\) ，现在所有存在的数位组成的 \(lcm\) 为 \(k\) 。问题在于这样数组大小会达到 \(18\times2520\times2520\) ，显然会 \(MLE\) 。

发现其实 \(k\) 能取到的值并不多，可以考虑用离散化的方法把 \(2520\) 的所有因数都离散化，这样就可以将 \(k\) 这一维大大缩减到 \(50\) ，然后按照常规的数位DP来处理即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll dp[20][2521][50];
ll num[20];
ll l,r;
int mp[2521],fmp[50],mcnt;
int t;

int gcd(int x,int y){
    return (y==0)?x:gcd(y,x%y);
}



ll dfs(int dep,int mod,int lcm,bool flag){
    if(dep==-1)
        return (mod%fmp[lcm]==0)?1:0;
    if(dp[dep][mod][lcm]!=-1 && flag==0)
        return dp[dep][mod][lcm];
    int limit=flag?num[dep]:9;
    ll ret=dfs(dep-1,(mod*10)%2520,lcm,(flag && limit==0));
    for(int i=1;i<=limit;++i)
        ret+=dfs(dep-1,(mod*10+i)%2520,mp[fmp[lcm]*i/gcd(fmp[lcm],i)],(flag && limit==i));
    if(flag==0)
        dp[dep][mod][lcm]=ret;
    return ret;
}



ll solve(ll x){
    int cnt=-1;
    while(x){
        num[++cnt]=x%10;
        x/=10;
    }
    return dfs(cnt,0,1,1);
}


int main(){
    memset(dp,-1,sizeof dp);
    for(int i=1;i<=2520;++i){
        if(2520%i==0){
            mp[i]=++mcnt;
            fmp[mcnt]=i;
        }
    }
    scanf("%d",&t);
    while(t--){
        scanf("%lld %lld",&l,&r);
        printf("%lld\n",solve(r)-solve(l-1));
    }
    return 0;
}