Codeforces 55D. Beautiful numbers
题意
求[L,R]区间内有多少个数满足：该数能被其每一位数字都整除（如12，24，15等）。
思路
一开始以为是数位DP的水题，觉得只需要记录搜到当前位出现了哪些数字作为状态即可，明显是假算法...感觉这是一道数位DP好题。可以这样思考：一个数要想被其各位数字分别都整除，等价于它被那些数字的LCM整除。因此记录当前位，当前数对（1~9的LCM）取模的结果，当前出现的数字的LCM这三个值作为状态才合理，即dp[pos][sum][lcm]。不过有一点需要注意，1-9的LCM的值会达到2520，直接存的空间复杂度是不对的，而1-9的数字任意组合的LCM明显没有那么多个，因此考虑离散化这些LCM，即可压缩空间。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<cstring>
#include<cmath>
#include<functional>
#include<string>
#define dd(x) cout<<#x<<" = "<<x<<" "
#define de(x) cout<<#x<<" = "<<x<<"
"
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef priority_queue<int> BQ;
typedef priority_queue<int,vector<int>,greater<int> > SQ;
const int maxn=5e3+10,mod=1e9+7,INF=0x3f3f3f3f;
int LCM,dig[30],id[maxn];
ll dp[30][maxn][100];
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
ll Lcm(ll a,ll b)
{
return a*b/gcd(a,b);
}
void init()
{
int num=0;
LCM=1;
for (int i=1;i<=9;++i)
LCM=Lcm(LCM,i);
for (int i=1;i<=LCM;++i)
if (LCM%i==0)
id[i]=num++;
memset(dp,-1,sizeof(dp));
}
ll dfs(int pos, int sum, int lcm, int lit)
{
if (pos==-1)
return sum%lcm==0;
if (!lit&&dp[pos][sum][id[lcm]]!=-1)
return dp[pos][sum][id[lcm]];
int up=lit?dig[pos]:9;
ll cnt=0;
for (int i=0;i<=up;++i)
{
int ns=(sum*10+i)%LCM,nl=i==0?lcm:Lcm(lcm,i);
cnt+=dfs(pos-1,ns,nl,lit&&i==dig[pos]);
}
if (!lit)
dp[pos][sum][id[lcm]]=cnt;
return cnt;
}
ll count(ll n)
{
int pos=0;
while (n)
{
dig[pos++]=n%10;
n/=10;
}
return dfs(pos-1,0,1,1);
}
int main()
{
init();
int T;
cin>>T;
while (T--)
{
ll l,r;
cin>>l>>r;
cout<<count(r)-count(l-1)<<endl;
}
return 0;
}