Problem: Example

Input

20


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

typedef tuple<int,int,int,int,int> tpl;

string digs;
int dig_sum;
ll dig_mul;
int N;
ll dp[15][200000][3];

// prime factor??¨, ????????????????????¨
int to_index[43][29][15][15][127];
tpl to_pf[200000];
int index_size;
ll to_mul_ary[43][29][15][15];

tpl pf[11];

ll to_mul(int two, int three, int five, int seven){
    if(to_mul_ary[two][three][five][seven]>=0) return to_mul_ary[two][three][five][seven];
    ll res = 1;
    for(int i=0;i<two;i++)res *= 2;
    for(int i=0;i<three;i++)res *= 3;
    for(int i=0;i<five;i++)res *= 5;
    for(int i=0;i<seven;i++)res *= 7;
    return to_mul_ary[two][three][five][seven] = res;
}

ll dfs(int pos, int pf_idx, int is_lower){
    if(dp[pos][pf_idx][is_lower] >= 0) return dp[pos][pf_idx][is_lower];
    ll res = 0;
    if(pos == N){
        tpl t = to_pf[pf_idx];
        int sum = get<4>(t);
        if(dig_sum > sum) res = 1;
        else if(dig_sum == sum){
            ll a = to_mul(get<0>(t), get<1>(t), get<2>(t), get<3>(t));
            if(a < dig_mul) res = 1;
            else if(a == dig_mul) res = (is_lower == 1);
        }
    }
    else{
        // ????????°???????????¨?????????
        for(int i = 0; i < 10; i++){
            int n_is_lower = is_lower;
            if(n_is_lower == 0){
                if(digs[pos] - '0' > i) n_is_lower = 1;
                else if(digs[pos] - '0' < i)n_is_lower = 2;
            }
            // ?????¨????????°???????????????2,3,5,7?????°????¢?????????????
            // ?¢???????????????°???????????????, ?¨?????????????
            int a = get<0>(to_pf[pf_idx]) + get<0>(pf[i+1]);
            int b = get<1>(to_pf[pf_idx]) + get<1>(pf[i+1]);
            int c = get<2>(to_pf[pf_idx]) + get<2>(pf[i+1]);
            int d = get<3>(to_pf[pf_idx]) + get<3>(pf[i+1]);
            int sum = get<4>(to_pf[pf_idx]);
            int n_sum = sum + i;
            if(to_index[a][b][c][d][n_sum] == -1){
                to_index[a][b][c][d][n_sum] = index_size++;
                to_pf[index_size-1] = make_tuple(a,b,c,d,n_sum);
            }
            res += dfs(pos + 1, to_index[a][b][c][d][n_sum], n_is_lower);
        }
    }
    return dp[pos][pf_idx][is_lower] = res;
}

int main(){

    // 1-10?????°???????????????, ???????????????2,3,5,7?????°????¨????????????????
    pf[1] = make_tuple(0,0,0,0,0);
    pf[2] = make_tuple(1,0,0,0,0);
    pf[3] = make_tuple(0,1,0,0,0);
    pf[4] = make_tuple(2,0,0,0,0);
    pf[5] = make_tuple(0,0,1,0,0);
    pf[6] = make_tuple(1,1,0,0,0);
    pf[7] = make_tuple(0,0,0,1,0);
    pf[8] = make_tuple(3,0,0,0,0);
    pf[9] = make_tuple(0,2,0,0,0);
    pf[10] = make_tuple(1,0,1,0,0);
    
    memset(to_mul_ary, -1,sizeof(to_mul_ary));
    memset(dp,-1,sizeof(dp));
    memset(to_index, -1, sizeof(to_index));
    
    cin>>digs;
    N = digs.size();

    dig_mul = 1;
    // digs???sum??¨prod????¨????????????????
    for(int i=0;i<N;i++){
        int dig = (digs[i] - '0');
        dig_sum += dig;
        dig_mul *= (dig + 1);
    }
    // 0,0,0,0???index 0?????????
    to_index[0][0][0][0][0] = 0;
    to_pf[0] = make_tuple(0,0,0,0,0);
    index_size++;
    cout<<dfs(0, 0, 0)<<endl;
    
    return 0;
}