Description
一个数x各个数位上的数之积记为\(f(x)\) <不含前导零>
求[L,R)中满足\(0<f(x)<=n\)的数的个数
solution
最后\(f(x)\)可以拆分成2,3,5,7的乘积，我们就将 \(2,3,5,7\) 压进状态，然后就是基础的数位DP，分是否严格小于两种状态转移即可
具体实现需要一些技巧:
预处理出每一个数含有 \(2,3,5,7\)的个数
预处理出 \(2,3,5,7\) 的幂，方便剪枝
注意数字不能含有 \(0\)，我们每DP一位，要新加入 \([1,9]\) 的状态，即前导零的情况
还有一种解法是用 \(map\) 压乘积，网上大部分都是这么做的，也能通过，且简洁很多
tips：代码实现比较简单，但我已不想再多看一眼我的代码....
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=36;
typedef long long ll;
int m,lim[6],pri[6]={0,2,3,5,7};ll f[21][2][33][21][15][13];
char S[22];
ll m5[N],m2[N],m7[N],m3[N];int v[15][6];
ll solve(int *a,int n){
if(n==1){
int ret=0;
for(int i=1;i<a[1];i++)ret+=(i<=m);
return ret;
}
ll x,mu;memset(f,0,sizeof(f));
for(int i=1;i<n;i++){
if(i==1)for(int j=1;j<=a[i];j++)
f[i][j<a[i]][v[j][1]][v[j][2]][v[j][3]][v[j][4]]++;
else for(int j=1;j<=9;j++)
f[i][1][v[j][1]][v[j][2]][v[j][3]][v[j][4]]++;
for(int j=0;j<=lim[1];j++){
if(m2[j]<=m)
for(int k=0;k<=lim[2];k++){
if(m2[j]*m3[k]<=m)
for(int g=0;g<=lim[3];g++){
if(m2[j]*m3[k]*m5[g]<=m)
for(int b=0;b<=lim[4];b++){
mu=m2[j]*m3[k]*m5[g]*m7[b];
if(mu>m)break;
x=f[i][1][j][k][g][b];
if(x)
for(int d=1;d<=9 && mu*d<=m;d++)
f[i+1][1][j+v[d][1]][k+v[d][2]][g+v[d][3]][b+v[d][4]]+=x;
x=f[i][0][j][k][g][b];if(!x)continue;
for(int d=1;d<=a[i+1] && mu*d<=m;d++)
f[i+1][d<a[i+1]][j+v[d][1]][k+v[d][2]][g+v[d][3]][b+v[d][4]]+=x;
}
}
}
}
}
for(int i=n;i<=n;i++)
for(int j=1;j<=9;j++)
f[i][1][v[j][1]][v[j][2]][v[j][3]][v[j][4]]++;
ll ret=0;
for(int j=0;j<=lim[1];j++)
if(m2[j]<=m)
for(int k=0;k<=lim[2];k++)
if(m3[k]*m2[j]<=m)
for(int g=0;g<=lim[3];g++)
if(m2[j]*m3[k]*m5[g]<=m)
for(int b=0;b<=lim[4];b++){
if(m2[j]*m3[k]*m5[g]*m7[b]>m)break;
ret+=f[n][1][j][k][g][b];
}
return ret;
}
int s1[22],s2[22],l1,l2;
void work()
{
scanf("%d",&m);
for(int i=1;i<=4;i++)lim[i]=log(m+1)/log(pri[i]);
m2[0]=1;for(int i=1;i<=lim[1];i++)m2[i]=m2[i-1]<<1;
m3[0]=1;for(int i=1;i<=lim[2];i++)m3[i]=m3[i-1]*3;
m5[0]=1;for(int i=1;i<=lim[3];i++)m5[i]=m5[i-1]*5;
m7[0]=1;for(int i=1;i<=lim[4];i++)m7[i]=m7[i-1]*7;
v[2][1]=1;v[3][2]=1;v[4][1]=2;v[6][1]=1;v[6][2]=1;
v[5][3]=1;v[7][4]=1;v[8][1]=3;v[9][2]=2;
scanf("%s",S+1);l1=strlen(S+1);
for(int i=1;i<=l1;i++)s1[i]=S[i]-'0';
scanf("%s",S+1);l2=strlen(S+1);
for(int i=1;i<=l2;i++)s2[i]=S[i]-'0';
ll ans=solve(s2,l2)-solve(s1,l1);
printf("%lld\n",ans);
}
int main()
{
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
work();
return 0;
}