codeforces-55D-完美数(数位DP)

题目链接

D. Beautiful numbers

思路

很明显用数位DP来写，那么怎么维护状态呢？一个数能够整除任一位数我们转化成这个数可以整除他们的最小公倍数。
那么包含1~9的最小公倍数是2520.当我们到最后一个数字的时候判断余数是否能够整除当前的lcm就可以了。但是有一个问题。
如果按照上述的思路，我们需要维护一个三维DP数组，也就是dp[50][2520][2520]，第一位表示位置，第二位表示当前的公倍数，第三位表示当前的余数，那么这个数组肯定超内存了。
所以我们考虑离散化，实际上他的公倍数只有48个，就是1-9的任意组合，那么我们把中间位置的离散成50大小的就可以写了。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
ll dp[20][50][2550];
int Hash[2550];
int cnt;
int a[50];
ll dfs(int pos,int remain,int Lcm,bool limit)
{
	if(pos==-1)return remain%Lcm?0:1;
	if(!limit&&dp[pos][Hash[Lcm]][remain]!=-1)return dp[pos][Hash[Lcm]][remain];
	ll temp = 0;
	int up=limit?a[pos]:9;
	for(int i=0;i<=up;i++)
	{
		temp += dfs(pos-1,(remain*10+i)%2520,i==0?Lcm:lcm(Lcm,i),limit&&i==up);
	} 
	if(!limit)dp[pos][Hash[Lcm]][remain]=temp;
	return temp;
}
ll solve(ll x)
{
	int pos = 0;
	while(x)
	{
		a[pos++]=x%10;
		x/=10;
	}
	return dfs(pos-1,0,1,true);
}
int main()
{   int t;
    scanf("%d",&t);
	for(int i=1;i<=2520;i++)
	if(2520%i==0)Hash[i]=cnt++;
	memset(dp,-1,sizeof(dp));
	while(t--)
	{
		ll l,r;
		cin>>l>>r;
		printf("%I64d\n",solve(r)-solve(l-1));
	}
}