题目大意
求有多少个不大于 \(n\) 的正整数，使得该正整数各位乘积不大于 \(k\)。
思路分析
观察数据范围，首先考虑数位 DP。
考虑设计记忆化搜索函数 dfs(int pos,bool limit,bool lead0,int mul) 表示当前枚举到第 \(\text{pos}\) 位，第 \(\text{pos}\) 位是否受到限制，是否存在前导零，当前乘积为 \(\text{mul}\) 时的满足条件的数的个数。同时设 \(f_{\text{pos},\text{mul}}\) 表示在没有前导零，没有限制的条件下的记忆化数组。
然后分类讨论一下：
设当前枚举的数为 \(i\)。
-
当存在前导零，且 \(i=0\) 时，\(\text{mul}\) 不变。
-
当存在前导零，且 \(i\not =0\) 时，\(\text{mul}=i\)。
-
当不存在前导零时，\(\text{mul}=\text{mul}\times i\)。
然后套板子就可以了。
注意乘积的值域可能很大，但状态不会很多，因此 \(f\) 可以用 map 储存。
代码
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <map>
using namespace std;
const int N=20;
#define int long long
int n,k;
int a[N];
map<int,int> f[N];//使用 map 储存 f
int dfs(int pos,bool limit,bool lead0,int mul){
if(!pos) return mul<=k;//边界条件
if(!limit&&!lead0&&f[pos].count(mul))
return f[pos][mul];//记忆化
int up=limit?a[pos]:9,res=0;//上届
for(int i=0;i<=up;i++){
int tmp;
if(lead0&&i==0) tmp=mul;
else if(lead0&&i!=0) tmp=i;
else tmp=mul*i;//分类讨论
res+=dfs(pos-1,limit&&i==up,lead0&&i==0,tmp);//直接累加
}
if(!limit&&!lead0) f[pos][mul]=res;
return res;
}
int solve(int x){
int len=0;
while(x){//拆分数位
a[++len]=x%10;
x/=10;
}
return dfs(len,1,1,0);
}
signed main(){
scanf("%lld%lld",&n,&k);
cout<<solve(n)-1<<'\n';//注意 0 会被计算在内，需减去
return 0;
}