题目链接：http://codeforces.com/problemset/problem/55/D
题意：一个美丽数就是可以被它的每一位的数字整除的数。
给定一个区间，求美丽数的个数。
显然这是一道数位dp，就是满足一个数能被所有位数的lcm整除即可。
一般都会设dp[len][mod][LCM]，mod表示余数，LCM表示前len位的lcm。
但是如果直接裸mod会很复杂，于是再想lcm{0,1,2,3,4,5,6,7,8,9}=2520;
而且lcm{a,b,c,d....}{a,b,c,d...表示各个位数)去重之后能被lcm{0,1,2....9}
整除。我们要求的是sum%lcm(a,b,c,d..}==0,所以只要满足
sum%lcm(0,1,2,...9}%lcm(a,b,c,d..}==0即可。于是mod就可以表示为
sum%lcm(0,1,2,...9}为多少。但是mod<=2520 && LCM<=2520这样
肯定存不下，于是要考虑如何处理LCM，毕竟很明显0~9的最大公倍数种类不会
超过48个。于是可以考虑一下离散化一下LCM，
if 2520 % num == 0 -> LCM[num]=temp++;
这样dp的三维就可以设为dp[20][2520][48];
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;
typedef long long ll;
const int mmax = 2520;
ll n , m , dp[20][mmax][50];
int temp , dig[20] , LCM[mmax + 10];
ll gcd(ll a , ll b) {
return b > 0 ? gcd(b , a % b) : a;
}
ll lcm(ll a , ll b) {
return a / gcd(a , b) * b;
}
void init() {
temp = 0;
for(int i = 1 ; i <= mmax ; i++) {
if(mmax % i == 0) {
LCM[i] = temp++;
}
else {
LCM[i] = 0;
}
}
}
ll dfs(int len , int count , int mod , int flag) {
if(!len) {
return mod % count == 0;
}
if(!flag && dp[len][mod][LCM[count]] != -1) {
return dp[len][mod][LCM[count]];
}
int t = flag ? dig[len] : 9;
ll sum = 0;
for(int i = 0 ; i <= t ; i++) {
int Nextmod = (mod * 10 + i) % mmax;
int Nextcount;
if(i == 0) {
Nextcount = count;
}
else {
Nextcount = (int)lcm(count , i);
}
sum += dfs(len - 1 , Nextcount , Nextmod , flag && i == t);
}
if(!flag)
dp[len][mod][LCM[count]] = sum;
return sum;
}
ll Gets(ll x) {
memset(dig , 0 , sizeof(dig));
int len = 0;
if(x == 0) {
dig[++len] = 0;
}
while(x) {
dig[++len] = x % 10;
x /= 10;
}
return dfs(len , 1 , 0 , 1);
}
int main() {
int t;
scanf("%d" , &t);
init();
memset(dp , -1 , sizeof(dp));
while(t--) {
scanf("%I64d%I64d" , &n , &m);
printf("%I64d
" , Gets(m) - Gets(n - 1));
}
return 0;
}