题解 CF55D 【Beautiful numbers】
蒟蒻操作一波终于A过了这道水题
本蒟蒻前几天才学数位DP，个人感觉这道题与P2657 windy数有异曲同工之妙（真的只是个人感觉）
Warning：如果还不熟练数位DP康这道题可能会死大量脑细胞
与其他的黑题相比，这道题真的简单太多了（虽然我也是在题解dalao们的启发下做出来的），所以我打算写一篇通俗易懂点的题解，也算是对其他dalao们的补充
进入正题
先说在前面，因为数据量极大，所以一个个的枚举是不行的！！！ 所以我们可以将[l,r]的区间变成[1,r]-[1,l-1]，这就是所谓的差分。
为了解决这道题，我们还需要了解两点小学数学知识：
1.一个数如果可以被几个数整除，那么这个数也可以被那几个数的最小公倍数整除；
2."1,2,3,4,5,6,7,8,9"的最小公倍数为2520 （废话） 。
知道后我们就可以开始解题了。
首先，因为是DP，所以我们需要一个DP数组来将宝贵中间的运算结果储存下来，之后可以直接使用（因为DP使用的是DFS，所以也可以看作记忆化剪枝）。
接着，因为是数位DP，所以我们需要DP数组开一个维度来储存当前位数。
其次，因为最后要检测这个数是否满足条件： 能被它自己的每一位数上的数整除 （也就是被每一位上的数的最小公倍数整除），所以我们又需要开两个维度：一个存数的值，一个存这个数每一位上的数的最小公倍数。
但我们不难发现，想存9*10（18）是不可能的，又因为题目最后是检测这个数能否被每一位上的数的最小公倍数整除，假设这个数为A，那么A与（A%2520）其实是等效的，所以我们可以不存A而存（A%2520），这样问题就解决了
于是我们就开了一个数组：DP[20(因为总共就19位数)][2521][2521]（DP数组内的数据表示满足当前情况的 Beautiful numbers 的个数），准备直接开始跑，然后就可以坐等AC内存超限了。
所以问题又来了：数组开不下。于是我们思考怎么减小数组：第一二位已经到最小了，只能改第三维。我们通过计算发现，1~2520中，2520的因数只有48个，也就是满足条件的情况只有48种，所以第三维大小直接变为48（这到底是属于撞鸭还是离散化？蒟蒻傻傻分不清）
上代码（还有些细节部分会在代码中注释）
！！！因为借鉴了题解dalao们的思路，所以代码会很相像！！！
#define Tokisaki return //狂三我老婆！！！
#define Kurumi 0; //狂三赛高！！！
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define rint register int //加速用的，直接用int也可以
typedef long long ll;
using namespace std;
const int MOD=2520;
int t,book[MOD+1];
vector <int> shu;
ll l,r,dp[25][MOD+1][50]; //特别注意：DP数组一定要开long long类型，不然会炸
inline int gcd (int x,int y) //gcd函数，虽然STL里面自带（为__gcd），但还是自己手写了一个
{
if(x>y) swap(x,y);
if(y%x==0) return x;
return gcd(x,y%x);
}
inline int _lcm (int x,int y) //lcm函数，求最小公约数
{
return x*y/gcd(x,y);
}
inline void init() //初始化用的函数
{
memset(dp,-1,sizeof(dp)); //将DP数组初始化
rint num=0;
for(rint i=1;i<=MOD;i++) //离散化，将2520的因数们从1开始标记
{
if(MOD%i==0)
{
num++;
book[i]=num;
}
}
}
ll dfs(int pos,int he,int lcm,int sp) //数位DP主要内容
//pos:当前处理到第几位；
//he：pos位之前的数%2520；
//lcm：pos位之前的数的每一位数的最小公倍数；
//sp：特判当前是否为范围内的最大值
{
if(pos==-1) return he%lcm==0; //如果处理完了最后一位，数如果满足条件，返回1，否则返回0
if(sp==0&&dp[pos][he][book[lcm]]!=-1) return dp[pos][he][book[lcm]]; //如果不是最大值的情况，并且当前情况以处理过，直接返回值
ll ans=0;
int MAX=sp==1?shu[pos]:9; //如果前几位是最大值情况，那么当前位最大值为这一位的数，否则为9
for(rint i=0;i<=MAX;i++) //从0枚举
{
int next_he=(he*10+i)%MOD; //计算包含当前位时数的值
int next_lcm=lcm;
if(i)
{
next_lcm=_lcm(next_lcm,i);//计算包含当前位时所有位上的数的最小公倍数（当前位所选数不为0，如果为零就是原数）
}
ans+=dfs(pos-1,next_he,next_lcm,sp&&i==MAX); //向下搜索，如果前几位是最大值情况，并且当前位为最大值时，sp=1
}
if(sp==0) //如果不是最大值情况，记录运算结果
{
dp[pos][he][book[lcm]]=ans;
}
return ans;
}
inline ll work (ll num) //处理数据加求值函数
{
shu.clear(); //一定要记得清空
while(num) //将数值按为存入
{
shu.push_back(num%10);
num/=10;
}
return dfs(shu.size()-1,0,1,1); //从最高位开始搜索
}
int main ()
{
init(); //初始化
cin>>t;
for(int i=1;i<=t;i++)
{
cin>>l>>r;
cout<<work(r)-work(l-1)<<endl;
}
Tokisaki Kurumi //狂三我老婆，不服憋着
}那么这便是代码了（好像混入了什么奇怪的东西）