题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3679


解法： 比较裸的数位DP,dp[i][j][k]表示前i位，当前位数字为j,乘积为k（k保存的是离散化之后的值）,然后按照数位DP的做法去写就可以了。


///BZOJ 3679
///数位DP，离散化

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dp[20][10][6000];
///dp[i][j][k]前i位，当前位数字为j,乘积为k（k保存的是离散化之后的值）
LL l, r;
int digit[20];
int a[6000];
int n, tot, num;
map<LL,int>p;
///2,3,5,7

bool check(int a, int b, int c, int d){
    long long ans=1;
    for(int i=1; i<=a; i++) ans*=2;
    if(ans>n) return 0;
    for(int i=1; i<=b; i++) ans*=3;
    if(ans>n) return 0;
    for(int i=1; i<=c; i++) ans*=5;
    if(ans>n) return 0;
    for(int i=1; i<=d; i++) ans*=7;
    if(ans>n) return 0;
    return 1;
}

int cal(int a, int b, int c, int d){
    int ans=1;
    for(int i=1; i<=a; i++) ans*=2;
    for(int i=1; i<=b; i++) ans*=3;
    for(int i=1; i<=c; i++) ans*=5;
    for(int i=1; i<=d; i++) ans*=7;
    return ans;
}

long long f(LL x){
    LL ans=0;
    num=0;
    while(x){
        digit[++num]=x%10;
        x/=10;
    }
    for(int i=1; i<=num/2; i++) swap(digit[i],digit[num-i+1]);
    for(int i=1; i<num; i++)
        for(int j=1; j<=9; j++)
            for(int k=1; k<=tot; k++)
                ans += dp[num-i][j][k];
    LL sum=1;
    for(int i=1; i<=num; i++){
        for(int j=1; j<digit[i]; j++){
            for(int k=1; k<=tot; k++){
                if(a[k]*sum>n) break;
                ans+=dp[num-i+1][j][k];
            }
        }
        sum*=digit[i];
        if(sum>n||sum==0) break;
    }
    return ans;
}

int main(){
    scanf("%d", &n);
    for(int i=0; i<=31; i++){
        for(int j=0; j<=18; j++){
            for(int k=0; k<=13; k++){
                for(int l=0; l<=10; l++){
                    if(check(i,j,k,l)){
                        a[++tot]=cal(i,j,k,l);
                    }
                }
            }
        }
    }
    sort(a+1,a+tot+1);
    for(int i=1; i<=tot; i++) p[a[i]]=i;
    scanf("%lld%lld",&l,&r);
    for(int i=1; i<=9; i++) if(p[i]) dp[1][i][p[i]]=1;
    for(int i=1; i<=18; i++){
        for(int j=1; j<=9; j++){
            for(int q=1; q<=tot; q++){
                if(dp[i][j][q]){
                    for(int k=1; k<=9; k++){
                        if((long long)a[q]*k<=n && p[a[q]*k]) dp[i+1][k][p[a[q]*k]]+=dp[i][j][q];
                    }
                }
            }
        }
    }
    long long ans = f(r)-f(l);
    printf("%lld\n", ans);
    return 0;
}


DFS版本：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL dp[20][6000];
LL n;
int cnt,a[20];
map<LL,int> use;
LL dfs(int pos,LL chengji,bool lead,bool limit)
{
    if(chengji>n)
        return 0;
    if(use[chengji]==0)
    {
        use[chengji]=cnt++;
    }
    if(pos==-1)
    {
        if(chengji>0&&chengji<=n)
            return 1;
        return 0;
    }
    if(lead==1&&!limit&&dp[pos][use[chengji]]!=-1)
        return dp[pos][use[chengji]];

    int up=limit ? a[pos]:9;
    LL ret=0;
    for(int i=0;i<=up;i++)
    {
        if(i==0)
        {
            if(lead==true)
                ret+=dfs(pos-1,chengji*i,true,limit&&i==a[pos]);
            else
                ret+=dfs(pos-1,0,false,limit&&i==a[pos]);
        }
        else
        {
             if(lead==true)
                ret+=dfs(pos-1,chengji*i,true,limit&&i==a[pos]);
             else
                ret+=dfs(pos-1,i,true,limit&&i==a[pos]);
        }
    }

    if(!limit&&lead)
        dp[pos][use[chengji]]=ret;
    return ret;
}
LL solve(LL x)
{
    int pos=0;
    while(x)
    {
        a[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,0,false,true);
}
int main()
{
    memset(dp,-1,sizeof(dp));
    LL l,r;
    use.clear();
    cnt=1;

    scanf("%lld",&n);
    scanf("%lld%lld",&l,&r);
    LL ans=solve(r-1)-solve(l-1);
    printf("%lld\n",ans);
return 0;
}