CF55D Beautiful numbers

题目链接

题意分析

一看题意还有数据范围就是知道是数位DP

我们考虑一个数x被整除他所有非零位的数字 等于被整除所有非零位数字的最小公倍数

由于{1,2,3,4,5,6,7,8,9}的最小公倍数是2520 所以我们维护三个状态[i][j][k]表示第i位且对应%2520=j 最小公倍数是k的方案数

很明显合法的方案是j%k=0

直接设状态的话是[19][2521][2521] 会炸

我们发现 k一定是2520的一个因数 而2520因数有48个 这样可以把第三维压成[48]

这里的话直接DP不太方便 所以改用记忆化搜索

CODE:

#include<bits/stdc++.h>
#define MOD 2520
using namespace std;
int T,tot;
long long le,ri;
long long dp[20][MOD+10][50];
int vec[50],wt[MOD+10];
vector<int> G;
int gcd(int x,int y){return y ? gcd(y,x%y):x;}
int lcm(int x,int y){return y ? (x*y)/gcd(x,y):x;}
long long dfs(int nowat,int resmod,int nowlcm,bool limit)//limit是最高位的限制 防止在最高位的限制下计算方案导致超出原数范围
{
	if(!nowat) return resmod%nowlcm==0 ? 1:0;
	if(!limit&&dp[nowat][resmod][wt[nowlcm]]) return dp[nowat][resmod][wt[nowlcm]];
	int maxn=limit ? G[nowat]:9;
        long long tmp=0;
	for(int i=0;i<=maxn;++i) tmp+=dfs(nowat-1,(resmod*10+i)%MOD,lcm(nowlcm,i),limit&(i==maxn));
	if(!limit) dp[nowat][resmod][wt[nowlcm]]=tmp;
	return tmp;
}
long long solve(long long x)
{
	G.clear();G.push_back(-1);
	while(x) G.push_back(x%10),x/=10;
	return dfs((int)G.size()-1,0,1,1);
}
int main()
{
	for(int i=1;i<=MOD;++i) if(MOD%i==0) vec[++tot]=i,wt[i]=tot;
	scanf("%d",&T);
	while(T--) 
	{
		scanf("%lld%lld",&le,&ri);
		printf("%lld\n",solve(ri)-solve(le-1));
	}
	return 0;
}