BZOJ 3679 数字之积

发表于 | 分类于 |

其实蛮水的……比较套路……
考虑到一个十进制数各位数字之积只有可能有四个质因子 \(2,3,5,7\)，所以我们可以根据这个设状态。

即，DP 时记录四个质因子的指数和其他一些必要的东西，然后爆搜出 \(n\) 以下可能的指数组合并统计答案。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <cstring>
using namespace std;
const int LEN = 18;
const int num[4] = {2,3,5,7};
const int c[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 n,d[LEN + 5],len;
long long l,r;
long long ans;
long long f[LEN + 5][35][25][18][16][2];
long long dfs(int x,int _2,int _3,int _5,int _7,int lead,int top)
{
    if(_2 < 0 || _3 < 0 || _5 < 0 || _7 < 0)
        return 0;
    if(!x)
        return !_2 && !_3 && !_5 && !_7;
    if(!top && ~f[x][_2][_3][_5][_7][lead])
        return f[x][_2][_3][_5][_7][lead];
    long long ret = 0;
    int bound = top ? d[x] : 9;
    for(register int i = 0;i <= bound;++i)
    {
        if(!lead && !i)
            continue;
        ret += dfs(x - 1,_2 - c[i][0],_3 - c[i][1],_5 - c[i][2],_7 - c[i][3],lead && !i,top && i == bound);
    }
    if(!top)
        return f[x][_2][_3][_5][_7][lead] = ret;
    return ret;
}
int w;
void dfs(int x,int prod,int _2,int _3,int _5,int _7)
{
    ans += w * dfs(len,_2,_3,_5,_7,1,1);
    for(register int i = x;i < 4;++i)
        if(prod * num[i] <= n)
            dfs(i,prod * num[i],_2 + (i == 0),_3 + (i == 1),_5 + (i == 2),_7 + (i == 3));
}
int main()
{
    memset(f,-1,sizeof f);
    scanf("%d%lld%lld",&n,&l,&r),--l,--r;
    for(;r;r /= 10)
        d[++len] = r % 10;
    w = 1,dfs(0,1,0,0,0,0);
    len = 0;
    for(;l;l /= 10)
        d[++len] = l % 10;
    w = -1,dfs(0,1,0,0,0,0);
    printf("%lld\n",ans);
}