求 \([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;
}