题目链接：https://codeforces.com/contest/55/problem/D
题目大意：给你一段区间[l,r]，要求这段区间中可以整除自己每一位（除0意外）上的数字的整数个数，例如15，因为15既可以整除1也可以整除5，所以15符合要求。
(1 ≤ li ≤ ri ≤ 9 ·1018).
Examples
input
Copy
1
1 9
output
Copy
9
input
Copy
1
12 15
output
Copy
2 解题思路：很明显的数位dp,首先我们可以想一个数要整除它的每一位除0意外，那我们可以转化成可以整除它的每一位的最小公倍数即可。而我们可以直接求出1-9的最小公倍数为2520，取模不改变它们间的倍数关系，因为数很大所以我们每次可以对2520取模就可以了。所以我们可以很容易想到定义一个数组dp[20][2525][2525],dp[pos][mul][sta]表示的是第搜索到第pos位数值为mul（模2520后）每一位的最小公倍数为sta的合法数的个数，但我们发现这样状态数很多是会超时的，所以我们必须想办法进行优化，我们认真想想发现比2520小的数中并不是每一个数都有可能是1-9中某些数字的倍数，我们把2520中可能是1-9某些数字的倍数的数筛出来就好了，发现只有48个，我们把dp数组改为dp【20】【2525】【50】，这样就不会超时了，相当于做了一个离散化处理。
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
int a[],k[];
ll l,r,dp[][][];
ll dfs(int pos,int mul,int sta,int limit){
if(pos==) return mul%sta==;
if(!limit&&dp[pos][mul][k[sta]]!=-)
return dp[pos][mul][k[sta]];
int up=limit?a[pos]:;
ll ans=;
for(int i=;i<=up;i++){
if(i==){ //当该位为0时，不求最小公倍数
ans+=dfs(pos-,mul*%,sta,limit&&i==a[pos]);
}else{
int tmp=lcm(sta,i);
ans+=dfs(pos-,(mul*+i)%,tmp,limit&&i==a[pos]);
}
}
if(!limit&&dp[pos][mul][k[sta]]==-)
dp[pos][mul][k[sta]]=ans;
return ans;
}
ll solve(ll x){
int pos=;
while(x){
a[++pos]=x%;
x/=;
}
return dfs(pos,,,);
}
int main(){
memset(dp,-,sizeof(dp));
int t,cnt=;
cin>>t;
for(int i=;i<=;i++){
if(%i==)k[i]=++cnt; //2520%i不为0表示i一定不是1-9中某些数字的最小公倍数
}
while(t--){
cin>>l>>r;
cout<<solve(r)-solve(l-)<<endl;
}
return ;
}