题目链接http://codeforces.com/problemset/problem/55/D
分析
看到这道题的时候我想到的是状压DP，压一下0~9是否出现过，但发现之后就不好弄了，因为它不仅可能出现，而且还会出现很多次，看数据范围就知道暴力肯定不可能的，这数据大小就算跑一遍循环也能T掉，所以这里就要用到数位DP了。
状压DP是用一个十进制数来表示二进制的状态，本质上还是暴力，不过是优化了。常用到位运算
数位DP跟它也差不多，算是一种暴力，主要用来解决数位上计数的问题，比如本题。主要是通过记忆化搜索来实现
因为查询时查询一个区间很不方便，所以将他拆成两个区间相减的形式，这个地方应该不难看出来。
接下来就是数位DP的内容了，先考虑最原始的版本，因为我要一位一位的去考虑，所以位数占了一维，又因为要判断是否是这什么什么(Numbers)，所以位数所表示的十进制数也要存下来，那么怎么判断是不是这种数字呢？最坏的情况是含了0到9的所有数字，既然每个数字都能整除，那么必定可以整除它们的最小公倍数，所以公倍数也要占一维，于是定义(dp_{i,j,k})为还剩下(i)位，并且前(i)位表示的数为(j)，这(i)位数字的最小公倍数为(k)时的
答案是多少，这里解释一下(i)这一维，比如123456，前三位分别是1，2，3，表示的数即为123，然后就能通过枚举得到(dp_{i,j,k})=(sum_{i=0}^{Max})(dp_{i-1,j*10+i,lcm(k,i)}),lcm表示的就是最小公倍数，这个应该也能看懂，他其实就是暴力的枚举了每
一位上的数字。
这个数组开了之后肯定会MLE，考虑一下优化，1~9的最小公倍数为(5*7*8*9==2520)，也就是说第三维的状态不可能比2520还要大，但开2520还是会MLE，继续思考，1到2520很多数字我们都是用不到的，我们用到的实际上只有2520的因数，所以可以提前预处理出来，然后把第三维的状态改成最小公倍数对应的数字为(k)，相当于一个离散化。
最棘手的东西还是中间这一维，直接记录的话会发现它最大(9*10^{18})次方，那么有没有什么好的办法来压一下这个大小呢？先思考一下，我们最后判断的是什么，就是这个数(mod)它每个位数字上的最小公倍数是否==0，设这个数为(x)，最小公倍数为(lcm)，因为涉及到(mod)，所以从同余的角度来考虑。
引理:如果(a)是(b)的因子，那么(x)同余(x)%(b(mod)(a))
证明:因为(a)是(b)的因子，所以可以设(b=na，n)是正整数
不妨设(x=qb+r，r=0，1，2……b-1)
所以(x)(equiv)(x-qna)((mod)(a))
即(x)(equiv)(x-qb)((mod)(a))
(x-qb)即为(r)又因为(r)是(x)%(b)((mod)(a))
所以(x)(equiv)(x)%(b)((mod)(a))
有了这个引理，就好办多了，所有的lcm都一定是2520的因子，所以(x)(equiv)(x)%(2520)((mod)(lcm))
也就是说，(x)与(x)%(2520)实际上是等价的，那为什么我们不把它%一下，于是第二维也就只需要开2520，空间问题就解决了，加上之前的一些分析，这个问题基本解决。
细节
1.记忆化
反正都搜过了，不记白不记。但是记录的时候要注意，因为枚举每个位置的时候，不能超过这个数原本的值，超过了就会多记答案，所以当当前位是最大值的时候，不能记忆，同理返回值时也是。比如113，枚举百位时显然不能枚举到2，但当百位是0时，十位却能够到9，所以判断最大值时要保证每一位都是最大值。
2.longlong
这题不开longlong等着WA吧。
3.最大公约数和最小公倍数
最大公约数我用的辗转相除法，原理挺简单，就一直除，直到可以除尽为止。
最小公倍数就是两数的乘积除以最大公约数，这个就根据最小公倍数的定义自行理解吧
#include<iostream>
#define ll long long
using namespace std;
const int N=2525;
ll dp[20][N][50];
int p[N],hh,num[20],top;
int gcd(int a,int b){
return a%b?gcd(b,a%b):b;
}
int Lcm(int a,int b){
return b==0?a:a/gcd(a,b)*b;
}
ll dfs(int x,int sum,int lcm,bool ismx){
if(x==0)return sum%lcm==0;
if(!ismx&&dp[x][sum][p[lcm]])return dp[x][sum][p[lcm]];
int Max=ismx==1?num[x]:9;
ll ans=0;
for(int i=0;i<=Max;i++)
ans+=dfs(x-1,(sum*10+i)%2520,Lcm(lcm,i),ismx&&i==Max);
if(!ismx)dp[x][sum][p[lcm]]=ans;
return ans;
}
ll calc(ll x){
top=0;
while(x){
num[++top]=x%10ll;
x/=10ll;
}
return dfs(top,0,1,1);
}
int main(){
for(int i=1;i<=2520;i++)
if(2520%i==0)p[i]=++hh;
int t;
cin>>t;
while(t--){
ll l,r;
cin>>l>>r;
cout<<calc(r)-calc(l-1)<<'
';
}
}