题目链接：
hdu: http://acm.hdu.edu.cn/showproblem.php?pid=5179
bc(中文): http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=569&pid=1002
题解：
1、数位dp
dp[i][j]表示第i位的数值为j的时候所有合法的情况，转移方程为dp[i][j]+=dp[i-1][k](j%k==0)数位最多为10位，可以离线处理出来。
计算1到x（x十进制按位存储在arr[]里面）的所有合法情况：
对于第i位，另前面几位等于arr[j](j>i)，第i位为k<arr[i]，则满足条件arr[i+1]%k==0的都是合法的,累加起来即可，然后考虑完i位之后，继续讨论i-1位，一直做下去。
0要单独讨论，假设x的长度为tot，则考虑最高位dp[tot-1][0]（位数为第0位到第tot-1位）就是所有位数比tot小的合法数的总数，所以只要考虑最高位的0就可以了，其他位都不用考虑0。
区间[L,R]可以考虑为[1,R]-[1,L-1]。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int maxn = + ;
typedef long long LL; int a, b; LL dp[][];
void get_dp() {
memset(dp, , sizeof(dp));
dp[][] = ;
for (int i = ; i < ; i++) dp[][i] = ;
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
for (int k = ; k <= ; k++) {
if (j%k == ) {
dp[i][j] += dp[i - ][k];
}
}
if (j == ) dp[i][j] += dp[i - ][j];
}
}
} int arr[];
LL solve(int x) {
if (x == ) return ;
LL ret = ;
int tot = ;
memset(arr, , sizeof(arr));
while (x) {
arr[tot++] = x % ;
x /= ;
}
ret += dp[tot - ][];
for (int i = tot - ; i >= ; i--) {
if (arr[i] == ) break;
//表示从前几位不变第i位开始变小的所有合法数字
for (int j = arr[i] - ; j >= ; j--) {
if (arr[i + ] % j == ) {
ret += dp[i][j];
}
}
//最后一个数可以相等了，收尾了
if (i == && arr[i + ] % arr[i] == ) ret += dp[i][arr[i]];
//说明第i位不变的话就不可能合法了，不用继续做下去。
if (arr[i + ] % arr[i] != ) break;
}
return ret;
} int main() {
get_dp();
int tc;
scanf("%d", &tc);
while (tc--) {
scanf("%d%d", &a, &b);
LL ans = solve(b) - solve(a - );
printf("%lld\n", ans);
}
return ;
}
2、由于合法数不多，可以讨论离线暴力出一张表来，再二分答案。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std; const int maxn = + ;
typedef long long LL; const int tab[] = {
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,
}; int solve(int x) {
if (x == ) return ;
return upper_bound(tab, tab+, x)-tab;
} int a, b; int main() {
int tc;
scanf("%d", &tc);
while (tc--) {
scanf("%d%d", &a, &b);
int ans = solve(b) - solve(a - );
printf("%d\n", ans);
}
return ;
}
3、上一发正规模板化数位dp
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf typedef int LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII; const int INF=0x3f3f3f3f;
const LL INFL=10000000000000000LL;
const double eps=1e-; const double PI = acos(-1.0); //start---------------------------------------------------------------------- LL dp[][];
int arr[],tot;
LL dfs(int len,int j, bool ismax,bool iszer) {
if (len == ) {
return 1LL;
}
if (!ismax&&dp[len][j]>=) return dp[len][j]; LL res = ;
int ed = ismax ? arr[len] : ;
for (int i = ; i <= ed; i++) {
if(iszer&&i==) {
res+=dfs(len-,,ismax&&i==ed,iszer&&i==);
} else {
if(i==) continue;
if(j==) {
res+=dfs(len-,i,ismax&&i==ed,iszer&&i==);
} else {
if(j>=i&&j%i==) {
res+=dfs(len-,i,ismax&&i==ed,iszer&&i==);
}
}
} }
return ismax ? res : dp[len][j] = res;
} LL solve(LL x) {
tot = ;
while (x) {
arr[++tot] = x % ;
x /= ;
}
return dfs(tot,,true,true);
} int main() {
clr(dp,-);
int tc,kase=;
scf("%d",&tc);
while(tc--) {
LL l,r;
scf("%d%d",&l,&r);
prf("%d\n",solve(r)-solve(l-));
}
return ;
} //end-----------------------------------------------------------------------