Description

一个数x各个数位上的数之积记为f(x) <不含前导零>
求[L,R)中满足0<f(x)<=n的数的个数

Input

第一行一个数n
第二行两个数L、R

Output

一个数,即满足条件的数的个数

Sample Input

5
19 22

Sample Output

1

HINT

100%     0<L<R<10^18 , n<=10^9

Source

搜索都写挂..

考虑仅用1~9凑出的1e9内的数字最多只有5194个

于是我们把这个搜索一下 搜索出5194种情况 用map储存

搜索的时候不能规定位数 即使仅有18位 但因为我这种特殊写法 并不能规定搜索的位数

然后设dp[i][j]表示 位数为i  凑出第j种数字的方案数

预处理之后 用基础数位dp分别算出1~r-1 1~l-1的方案数 简单容斥

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论