题目描述
难度分:$2024$
输入$N(1 \leq N \leq 10^{18})$和$K(1 \leq K \leq 10^9)$。
问：有多少个不超过$N$的正整数，其数位乘积不超过$K$？
输入样例$1$
13 2
输出样例$1$
5
输入样例$2$
100 80
输出样例$2$
99
输入样例$3$
1000000000000000000 1000000000
输出样例$3$
841103275147365677
算法
数位DP
不知道是不是要放假了的原因，灵佬今天选的这道题虽然难度分不低，但是非常“模板”，只要分析清楚状态数量的上界，可以说就是一道数位DP的板子题。先将$N$转化为字符串$s$，其长度为$n$。
状态定义
$dp[i][mu][islimit][isnum]$表示从数位$i$开始填完最后一个数位$n-1$（数位从高到低用$0$起始标号），能够得到的数位积不超过$K$，且数字大小不超过$N$的数字个数。其中$mu$表示数位$[0,i)$的乘积，$islimit$表示前面的数位是否贴合上界，$isnum$表示前面的数位是否填过数字。
状态转移
$base$ $case$：
很显然，当$i \geq n$时，所有数位就全部填完了，如果$isnum=1$且$mu \leq K$，说明得到了一个符合题意的数字。
一般情况：
如果$isnum=0$，那么当前数位$i$可以继续不填数，状态转移方程为
$dp[i][mu][islimit][isnum]=dp[i+1][mu][0][isnum]$
否则，当前数位尝试填$d \in [1-isnum,ub]$。如果前面的数位$[0,i)$贴合上界，$ub=s[i]$；不贴合上界，则$ub=9$。状态转移方程为
$dp[i][mu][islimit][isnum]=\Sigma_{d=1-isnum}^{ub}dp[i+1][mu \times d][islimit \land digit=d][1]$
复杂度分析
在这个题的数据范围之下，通过打表，发现状态中$mu$的取值最多就是$A=36000$多，因此在最差情况下状态的个数也只有一百多万，而状态转移又是常数级别，因此时间复杂度为$O(An)$（$n$就是题干中数字$N$的数位个数）。
空间消耗主要在于状态的存储，和时间复杂度是一个级别的。
C++ 代码
from functools import lru_cache
x, k = map(int, input().split())
s = str(x)
n = len(s)
@lru_cache(None)
def dfs(i: int, mu: int, islimit: int, isnum: int) -> int:
if i >= n:
return 1 if isnum and mu <= k else 0
digit = int(s[i])
cnt = dfs(i + 1, mu, 0, 0) if not isnum else 0
ub = digit if islimit else 9
for d in range(1 - isnum, ub + 1):
cnt += dfs(i + 1, mu*d, islimit and digit == d, 1)
return cnt
res = dfs(0, 1, 1, 0)
dfs.cache_clear()
print(res)
