BZOJ 3679.数字之积

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

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

代码:

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);
}

arknights