题意：求区间[x , y]中beautiful number的个数，a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits.
分析：一个数能被它的所有非零数位整除，则能被它们的最小公倍数整除，而1到9的最小公倍数为2520，数位DP时我们只需保存前面那些位的最小公倍数就可进行状态转移，到边界时就把所有位的lcm求出了，为了判断这个数能否被它的所有数位整除，我们还需要这个数的值，显然要记录值是不可能的，其实我们只需记录它对2520的模即可，这样我们就可以设计出如下数位DP：dfs(pos,mod,lcm,f),pos为当前位，mod为前面那些位对2520的模，lcm为前面那些数位的最小公倍数，f标记前面那些位是否达到上限，这样一来dp数组就要开到19*2520*2520，明显超内存了，考虑到最小公倍数是离散的，1-2520中可能是最小公倍数的其实只有48个，经过离散化处理后，dp数组的最后一维可以降到48，这样就不会超了。
View Code
#include <stdio.h> #include <string.h> #define N 19 #define MOD 2520 typedef __int64 LL; int t[200],cnt; LL dp[N][MOD][48]; int digit[N]; int GCD(int a,int b) { while(a%b) { int tmp=b; b=a%b; a=tmp; } return b; } int LCM(int a,int b) { return a/GCD(a,b)*b; } int bs(int x) { int mid,min=0,max=cnt; while(min+1!=max) { mid=min+max>>1; if(t[mid]>x) max=mid; else min=mid; } return min; } LL dfs(int pos,int mod,int lcmid,int f) { if(pos==-1) return (mod%t[lcmid])?0:1; if(!f&&dp[pos][mod][lcmid]!=-1) return dp[pos][mod][lcmid]; int max=f?digit[pos]:9; LL ret=0; for(int i=0;i<=max;i++) { int nmod=(mod*10+i)%MOD; int nlcmid=lcmid; if(i) nlcmid=bs(LCM(t[lcmid],i)); ret+=dfs(pos-1,nmod,nlcmid,f&&i==max); } if(!f) dp[pos][mod][lcmid]=ret; return ret; } LL cal(LL x) { int pos=0; while(x) { digit[pos++]=x%10; x/=10; } return dfs(pos-1,0,0,1); } void init() { cnt=0; for(int i=1;i<=MOD;i++) { if(MOD%i==0) t[cnt++]=i; } memset(dp,-1,sizeof(dp)); } int main() { int t; init(); scanf("%d",&t); while(t--) { LL x,y; scanf("%I64d%I64d",&x,&y); printf("%I64d\n",cal(y)-cal(x-1)); } return 0; }