/*
漂亮数定义：可以整除任意数位上的数
求出区间[l,r]之间的漂亮数个数
因为
dp[i][j][k]：i位前模lcm的值是j，i位前lcm是k的漂亮数个数
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[25][
2600][
60],has[
2600],a[
25],len,tot;
void init(){
//2520最多也就51个约数
for(
int i=
1;i<=
2520;i++
)
if(
2520%i==
0)has[i]=++
tot;
}
ll LCM(ll a,ll b){return a*b/
__gcd(a,b);}
ll dfs(ll pos,ll mod,ll lcm,ll lim){
if(pos==
0)
return mod%lcm==
0;
if(!lim && dp[pos][mod][has[lcm]]!=-
1)
return dp[pos][mod][has[lcm]];
ll res=
0,num=lim?a[pos]:
9;
for(
int i=
0;i<=num;i++
){
ll c_mod=(mod*
10+i)%
2520;
ll c_lcm=
lcm;
if(i)c_lcm=
LCM(lcm,i);
res+=dfs(pos-
1,c_mod,c_lcm,lim&&i==
num);
}
if(!lim)dp[pos][mod][has[lcm]]=
res;
return res;
}
ll calc(ll x){
len=
0;
memset(a,0,
sizeof a);
while(x){
a[++len]=x%
10;
x/=
10;
}
return dfs(len,
0,
1,
1);
}
int main(){
init();
int t;
cin>>
t;
memset(dp,-
1,
sizeof dp);
while(t--
){
ll A,B;
cin>>A>>
B;
cout<<calc(B)-calc(A-
1)<<
endl;
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10726552.html
