题目链接：
http://codeforces.com/problemset/problem/55/D
数位DP
题目描述：
一个数能被它每位上的数字整除（0除外），那么它就是beautiful number。问区间[a,b]上有多少个beautiful number。如102就是一个beautiful number，因为它能整除1,2。14不是，因为14不能整除4.
解法：
数位DP，设dp[i][j][k]为累计到第i为，公倍数为j，模lcm(1,2,```,9)=2520的余数为k的数的个数。注意到两个事实，要求某个数能整除它的每一个非0位上的数字，那么等价于将这些数字求一个最小公倍数，如果这个数能整除它的最小公倍数，自然就是beautiful number。已知lcm（1,2，···，9） = 2520，一个数一定能写成k+2520*x这样的形式，其中0<k<2520。设组成这个数的非0数字的最小公倍数为j,就有（k+2520*x）%j = k%j.同时能知道2520的因子（不一定是素数因子）一共有48个，所以离散的存储这些数，同时用ra[i]，记录在离散数组中的编号。
贴代码：
#include <cstdio>
#include <cstring>
const int mod = ;
using namespace std;
typedef long long int LL;
template<typename T>T gcd(T a,T b)
{
return b==?a:gcd(b,a%b);
}
template<typename T>T lcm(T a,T b)
{
if(a*b == ) return a?a:b;
return a/gcd(a,b)*b;
}
int ra[mod+];
int lm[];
LL dp[][][mod+];
int e[];
int p[];
void init()
{
e[] =;
for(int i=; i<; ++i)
e[i] = e[i-]*%mod; //e[i]表示10^i%2520的余数
int cnt=;
for(int i=; i<=mod; ++i)
if(mod%i == ) lm[cnt] = i,ra[i] = cnt,++cnt;//记录2520的因子
//ra记录这个因子在离散化存因子中的编号
}
void onceInit()
{
init();
dp[][][] = ;
for(int i=; i<; ++i)
{
for(int t=; t<; ++t)
{
for(int j=; j<; ++j)
{
int d = lcm(lm[j],t);
int jj = ra[d];
for(int k=; k<; ++k)
{
int kk = (t*e[i-]+k)%mod;
dp[i][jj][kk] += dp[i-][j][k];
}
}
}
}
}
int splitInt(LL x)//将数拆成一位一位的存在ｐ数组中
{
int i;
for(i=; x; ++i)
p[i] = x%,x /= ;
return i;
}
LL solve(LL x)//统计从0-x中有多少个beautiful number，x不包含在内
{
LL ans =;
int len = splitInt(x);
int cu1=,cu2=;//前面数的公倍数，余数
for(int i=len-; i> ; --i)
{
for(int t=; t<p[i]; ++t)
{
for(int j=; j<; ++j)
{
int d = lcm(lm[j],t);
d = lcm(d,cu1);//这是真正的公倍数
int tmp = (cu2+t)*e[i-]%d;//k+tmp = l*d这样的k会是解
for(int k=(d-tmp)%d; k < ; k +=d)
ans += dp[i-][j][k];
}
}
cu1=lcm(cu1,p[i]);//更新前面的余数和倍数
cu2 = (cu2+p[i])*%mod;
}
return ans;
}
int main()
{
// freopen("in.c","r",stdin);
onceInit();
int t;
scanf("%d",&t);
while(t--)
{
LL a,b;
scanf("%I64d%I64d",&a,&b);
printf("%I64d\n",solve(b+) - solve(a));
}
return ;
}