[BZOJ1183] Umnozak

Description

求满足其本身乘以他所有数位的乘积在 ([a,b]) 之间的所有数字的个数。(b le 10^{18})。

Solution

记所有数位的乘积为 (digProd)，则显然 (digProd le 10^9)，而 (digProd) 的质因子只可能有 (2,3,5,7)，这样的数字非常少，于是我们考虑暴力枚举 (digProd)。

对于一个确定的 (digProd)，我们需要计算出这个范围内的满足数位乘积质因子个数限定的数字数量。

考虑数位 dp，设 (f[i][c_2][c_3][c_5][c_7]) 表示从高到低填入了 (i) 位，(2,3,5,7) 的s剩余数目分别为 (c_2,c_3,c_5,c_7) 的方案数，转移时只需要枚举最后一位填的数字即可。

注意：(c_2,c_3,c_5,c_7) 一定要是剩余个数，这样才可以复用。

设置 first,full 标记这种方式已经很套路了。

（又是自闭的一天）

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1000005;
const int M = 25;

const int facCnt[10][4]={
   {0,0,0,0},
   {0,0,0,0},
   {1,0,0,0},
   {0,1,0,0},
   {2,0,0,0},
   {0,0,1,0},
   {1,1,0,0},
   {0,0,0,1},
   {3,0,0,0},
   {0,2,0,0}
};

int a[M],len,f[M][M*2][M][M][M],C2,C3,C5,C7;

int dfs(int pos,int c2,int c3,int c5,int c7,int full,int first)
{
    if(pos==-1)
    {
        return c2==0 && c3==0 && c5==0 && c7==0 && !first;
    }
    if(f[pos][c2][c3][c5][c7]!=-1 && !first && !full)
    {
        return f[pos][c2][c3][c5][c7];
    }
    int ans=0,lim=full?a[pos]:9;
    if(first)
    {
        ans+=dfs(pos-1,c2,c3,c5,c7,full&&a[pos]==0,1);
    }
    for(int i=1;i<=lim;i++)
    {
        int n2=c2-facCnt[i][0];
        int n3=c3-facCnt[i][1];
        int n5=c5-facCnt[i][2];
        int n7=c7-facCnt[i][3];
        if(n2>=0 && n3>=0 && n5>=0 && n7>=0)
        {
            ans+=dfs(pos-1,n2,n3,n5,n7,full&&i==lim,0);
        }
    }
    if(!full && !first) f[pos][c2][c3][c5][c7]=ans;
    return ans;
}

int solve(int n)
{
    if(n==0) return 0;
    len=0;
    memset(a,0,sizeof a);
    while(n)
    {
        a[len++]=n%10;
        n/=10;
    }
    return dfs(len-1,C2,C3,C5,C7,1,1);
}

int solve(int dpLeft,int dpRight,int cnt2,int cnt3,int cnt5,int cnt7)
{
    C2=cnt2;
    C3=cnt3;
    C5=cnt5;
    C7=cnt7;
    return solve(dpRight);
}

int rangeLeft,rangeRight;

int calc(int n)
{
    int ans=0;
    int limit=sqrt(n);
    for(int c2=0;c2<2*M;c2++)
        for(int c3=0;c3<M;c3++)
            for(int c5=0;c5<M;c5++)
                for(int c7=0;c7<M;c7++)
                {
                    int prod=1;
                    int t2=c2,t3=c3,t5=c5,t7=c7;
                    while(t2&&prod*2<limit) --t2, prod*=2;
                    while(t3&&prod*3<limit) --t3, prod*=3;
                    while(t5&&prod*5<limit) --t5, prod*=5;
                    while(t7&&prod*7<limit) --t7, prod*=7;
                    if(t2+t3+t5+t7==0)
                    {
                        ans+=(solve(1,n/prod,c2,c3,c5,c7));
                    }
                }
    return ans;
}

signed main()
{
    ios::sync_with_stdio(false);

    cin>>rangeLeft>>rangeRight;
    
    memset(f,0xff,sizeof f);
    
    cout<<calc(rangeRight)-calc(rangeLeft-1)<<endl;
    return 0;
}