2023-09-01 11:29:13 solution
题意：
每次询问 \([l,r]\) 内有多少个数满足可以被所有非 \(0\) 数位整除。
思路
看到这个数据范围和题目描述，显然是数位 dp。
因为 \(1\sim 9\) 的最小公倍数是 \(2520\)，并且 \(2520\) 是其他所有 \(1\sim 9\) 子集的最小公倍数的倍数，所以我们只需要边对 \(2520\) 取模然后边算这个数的最小公倍数，然后最后看对 \(2520\) 取模的结果对最小公倍数取模是否为 \(0\) 即可（为 \(0\) 代表可以被这些公倍数整除）。
可是如果直接存一维余数，一维公倍数，一维长度，数组是 \(2520^2\times 20\)，显然炸了，我们发现公倍数最多只有 \(48\) 个，那就好做多了。
注意不要开对上界 \(lim\) 的记忆化，每次询问之间也不要清空，不然就相当于要跑 \(T\) 次 \(2520\times 48 \times 20\) 显然时间复杂度炸了，所以我们留着之前没有被限制的答案，对于现在的答案的贡献也是正确的，每次只需要多算被限制的即可。
\(Code\)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,mod=2520;
ll f[20][48][2520],A[20],to[2521];
ll dfs(int len,int mv,int lcm,bool lim){
if(!len)return !(mv%lcm);
if(!lim&&~f[len][to[lcm]][mv])return f[len][to[lcm]][mv];
int up=lim?A[len]:9;
ll res=0;
for(int i=0;i<=up;i++)
res+=dfs(len-1,(mv*10+i)%mod,((i==0||!(lcm%i))?lcm:(lcm*i/__gcd(lcm,i))),lim&(i==up));
return lim?res:(f[len][to[lcm]][mv]=res);
}
ll solve(ll n){
int len=0;
while(n){
A[++len]=n%10;
n/=10;
}
return dfs(len,0,1,1);
}
int main(){
memset(f,-1,sizeof(f));
for(int i=1,cnt=0;i<=mod;i++)if(!(mod%i))to[i]=cnt++;
ios::sync_with_stdio(0);cin.tie(0);
for(cin>>T;T--;){
ll l,r;
cin>>l>>r;
cout<<solve(r)-solve(l-1)<<endl;
}
}