神秘海螺是什么鬼
题意：
给定一个区间，求这个区间内“beautiful number”的个数，beautiful number定义：若一个数能被它每一位上的数除尽，那么我们就称这个数为beautiful number。
这道题由于数据贼大，写一个暴力一定是过不了的，但我还想试一下，就写了一个暴力枚举每一个数，取出它每一位上的数，若都能除尽，则记录一下答案，然后交了上去，结果你懂的......
这道题的正解要用到"数位DP",我们要开一个维度来存储当前处理到的数位,一个维度来存储对应位数的数的值,第三个维度存储当前组成第二维的数字的最小公倍数,这样当第一维结果为-1时可以通过第二维模上第三维是否为0来判断是否合格。而直接将输入的值放在第二维一定是放不下的,于是我们考虑,我们拿来取模的数一定在1~9之间,而1~9的所有数的最小公倍数是2520,由于2520可以被1~9之间的每一个数除尽,那么我们拿原数模上1~9中的一个数其实是和拿原数模上2520再模上那个数的结果是一样的.我们就可以将dp数组开成20*2521*2521的，还是不行，又由于我们第三维存的是最小公倍数，这个数一定是2520的一个因数（毕竟都是由1~9乘出来的），我们便可以把2520的每一个公因数离散化到一个数组中，由于2520共48个公因数，故第三维开50即可。
另外，在过程中我们可以用到记忆化来进行优化，若一种情况已经跑过，就不用再跑了，如123和223，由于在跑123时23两位的结果已经求得，在算223时直接用就行了，但是要注意，在最高位用记忆化时不能超了最高位的数字，如233你去用333跑出来的数一定是偏高的，故我们在记录和提取时注意判断最高位。
根据以上思路我们就可以求出1到某个数的答案，由于问题要求我们给出区间内的答案个数，最终我们输出右区间的答案减去左区间的答案就行。其他细节详见代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<vector> 5 using namespace std; 6 const int Mod=2520; 7 int t,book[Mod+1]; //book用于离散化 8 long long dp[25][Mod+1][50]; 9 vector<int>shu; //向量用于存储输入数字每一位数 10 long long gcd(long long x,long long y){ //计算最大公因数,为计算最小公倍数服务 11 if(x>y) swap(x,y); 12 if(y%x==0) return x; 13 return gcd(x,y%x); 14 } 15 long long Lcm(long long x,long long y){ //计算最小公倍数 16 return x*y/gcd(x,y); 17 } 18 void Init(){ 19 memset(dp,-1,sizeof(dp)); //初始化一次就行,虽然是多组数据,但前面的记忆化 20 long long tot=0; //仍然能被后面应用 21 for(int i=1;i<=Mod;++i){ 22 if(Mod%i==0){ 23 book[i]=++tot; //离散化 24 } 25 } 26 } 27 long long dfs(int pos,long long num,long long lcm,int high){ 28 if(pos==-1) return !(num%lcm)?1:0; //走到最后一位奇数 29 if(!high&&dp[pos][num][book[lcm]]!=-1) //不是最高位,可以使用记忆化 30 return dp[pos][num][book[lcm]]; 31 int up=high?shu[pos]:9; //如果是最高位,算到最高位的数字即可 32 long long ans=0; 33 for(int i=0;i<=up;++i){ 34 long long tnum=(num*10+i)%Mod; //组成新的数字 35 long long tlcm=lcm; 36 if(i){ 37 tlcm=Lcm(tlcm,i); 38 } 39 int cnt=high&&(i==up); //判断当前位是否为最高位 40 ans+=dfs(pos-1,tnum,tlcm,cnt); 41 } 42 if(!high) dp[pos][num][book[lcm]]=ans; //记忆化记录 43 return ans; 44 } 45 long long work(long long num){ 46 shu.clear(); //清空向量 47 while(num){ //将数字拆开 48 shu.push_back(num%10); 49 num/=10; 50 } 51 return dfs(shu.size()-1,0,1,1); 52 } 53 int main(){ 54 Init(); 55 int T; 56 scanf("%d",&T); 57 while(T--){ 58 long long n,m; 59 long long ans=0; 60 scanf("%lld%lld",&n,&m); 61 printf("%lld ",work(m)-work(n-1)); //记得开long long 62 } 63 return 0; 64 }