题意：求从l到r中的数能被自己的每一位整除的有多少个
如果x满足条件，那么 x %lcm{digit【i】}==0，又因为digit【i】只可能为1-9，lcm{1，，，9}=2520，所以x%2520%lcm{digit【i】}==0，这样只需存x%2520，节约了空间和时间
从1到10的最小公倍数的组合情况只有48，可以事先开一个数组存起来，indx【i】就是记录从1到 i 的组合情况的
#include<bits/stdc++.h> #define C 0.5772156649 #define pi acos(-1.0) #define ll long long #define mod 2520 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-7; const int N=20+10,maxn=1000000+10,inf=0x3f3f3f; ll dp[N][mod+10][50],digit[N],indx[mod+10]; ll gcd(ll a,ll b) { return b ? gcd(b,a%b) : a; } ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll dfs(int len,int sum,int prelcm,bool fp) { if(!len)return sum%prelcm==0; if(!fp&&dp[len][sum][indx[prelcm]]!=-1) return dp[len][sum][indx[prelcm]]; ll ans=0,fpmax=fp ? digit[len] : 9; for(int i=0;i<=fpmax;i++) { int nowlcm=prelcm; if(i)nowlcm=lcm(prelcm,i); ans+=dfs(len-1,(sum*10+i)%mod,nowlcm,fp&&i==fpmax); } if(!fp)dp[len][sum][indx[prelcm]]=ans; return ans; } ll solve(ll x) { memset(digit,0,sizeof digit); int len=0; while(x) { digit[++len]=x%10; x/=10; } return dfs(len,0,1,1); } int main() { ios::sync_with_stdio(false); cin.tie(0); int num=0; for(int i=1;i<=mod;i++) if(mod%i==0) indx[i]=num++; int t; cin>>t; memset(dp,-1,sizeof dp); while(t--) { ll l,r; cin>>l>>r; cout<<solve(r)-solve(l-1)<<endl; } return 0; } /******************** ********************/