题目大意：
定义：beautiful number，一种能整除它的所有非 0 数位的数字。
给你 l 和 r，请求出 [l,r] 中 beautiful number 的个数。
解题思路：
数位 DP 。
首先要指出的一点是：lcm(1,2,3, ... ,9) = 2520。则对于任何一个数 num，num = 2520k + num'，我们有 num % 2520 % t = num' % t = num % t (t = 1,2,3, ... , 9)，其实也不难理解：因为 2520k 必定被 t 整除，所以 num % t 其实就等于 num' % t 。下面是一个就 t % (x*n) % x = t % x 的严格证明：
设 t = k*x + t' 。则有 t%x = t' 。令 k = a*n+b，则 t % (x*n) % x = (k*x+t') % (x*n) % x = (a*n*x + b*x + t') % (n*x) % x = (b*x + t') % x = t' 。原等式得证。
如此一来，我们便可将所有的数字对着 2520 取一下模，压缩状态。
我们可以定义 dp[pos][now][prelcm]：其中 pos 表示当前遍历到的位置，now 表示当前数字的大小，prelcm 表示前面的几个数字的最小公倍数，如此我们需要定义 dp[20][2520][2521]，虽然已经十分优秀，但似乎还有点大？其实我们还可以用离散化来优化一下：虽说 lcm(1,2,3, ... ,9) = 2520，但我们绝对不可能取尽这两千多个数，你说对吧？
至于其他的，其实就都是套路了，数位 DP 其实也是有套路滴~
AC代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 using namespace std; 6 typedef long long ll; 7 const int MOD = 2520; 8 ll index[MOD+3]; 9 ll dp[22][MOD][50]; 10 int num[20]; 11 void init(){ 12 int cnt=0; 13 for(int i=1;i<=MOD;i++){ 14 if(MOD%i==0) index[i]=cnt++; 15 } 16 } 17 ll gcd(ll a,ll b){ 18 if(b==0) return a; 19 return gcd(b,a%b); 20 } 21 ll lcm(ll a,ll b){ 22 return a/gcd(a,b)*b; 23 } 24 ll dfs(int pos,int prelcm,int now,bool limit){ 25 if(pos==-1){ 26 if(now%prelcm==0) return 1; 27 return 0; 28 } 29 if(!limit&&dp[pos][now][index[prelcm]]!=-1) return dp[pos][now][index[prelcm]]; 30 int up=limit?num[pos]:9; 31 ll ret=0; 32 for(int i=0;i<=up;i++){ 33 int next=(now*10+i)%MOD; 34 int tlcm=prelcm; 35 if(i) tlcm=lcm(tlcm,i); 36 ret+=dfs(pos-1,tlcm,next,limit&&i==up); 37 } 38 if(!limit) dp[pos][now][index[prelcm]]=ret; 39 return ret; 40 } 41 ll solve(ll x){ 42 if(x==0) return 1; 43 int ind=0; 44 memset(num,0,sizeof(num)); 45 while(x){ 46 num[ind++]=x%10; 47 x/=10; 48 } 49 return dfs(ind-1,1,0,true); 50 } 51 int main() 52 { 53 init(); 54 memset(dp,-1,sizeof(dp)); 55 ll l,r; 56 int t; 57 scanf("%d",&t); 58 59 while(t--){ 60 scanf("%I64d%I64d",&l,&r); 61 printf("%I64d ",solve(r)-solve(l-1)); 62 } 63 return 0; 64 }