【Bzoj3679】数字之积

来源和评测点

Bzoj3679

题目

【题目大意】
一个数x各个数位上的数之积记为f(x) (不含前导零)
求[L,R)中满足0<f(x)<=n的数的个数。
【输入格式】
第一行一个数n
第二行两个数L、R
【输出格式】
一个数,即满足条件的数的个数
【限定条件】
0<L<R<10^18,n<=10^9
【输入样例】
5
19 22
【输出样例】
1
【样例解释】

刷题记录

30min

分析

请先思考后再展开

首先,按照题解的说法以2、3、5、7这些质因数组成的,
int范围内的大概只有几千个,所以可以记录下来,
排个序,搞个前缀和,然后用这个乘积来递推。

然后就是经典的套路了:
先不考虑前导零的问题预处理
然后处理位数<M的情况,
然后再一位位处理位数=M的情况即可

注意这一题因为是乘积,碰到0就要退出。

代码

请先思考后再展开

网上很多奇奇怪怪的代码呀
反正我这次尽全力优化了时间
并且清晰易懂

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
#ifdef WIN32
#define BIGN "%I64d"
#else
#define BIGN "%lld"
#endif
using namespace std;
typedef long long ll;
//*******************全局常量*******************
//*******************全局定义*******************
ll r2[40],r3[40],r5[40],r7[40],r10[40];
ll f[20][10000];
int cnt;int g[10000];
//*******************实现*******************
int num[20],ln;
ll dp(ll x,int n)
{
ll xx=x;ln=0;
while(xx>0) num[++ln]=int(xx%10),xx/=10;
ll ans=0,pst=1;
for(int i=ln;i>=1;i--)
for(int k=1;k<=cnt;k++)
ans+=f[i][k];//位数<ln
for(int i=ln;i>=1;i--)
{
int now=num[i];
for(int k=1;k<=cnt;k++)
for(int j=1;j<now;j++)
if(pst*ll(j)*ll(g[k])<=ll(n)) ans+=f[i][k];//位数=ln
pst*=ll(now);
if(!pst or pst>ll(n)) return ans;//无贡献
}
return ans+(pst<=ll(n));//最后这个是无法统计的x自己
}
//*******************主函数*******************
int main()
{
memset(f,0,sizeof(f));
r2[0]=r3[0]=r5[0]=r7[0]=r10[0]=1;//debug
for(int i=1;i<=35;i++) r2[i]=r2[i-1]*2;
for(int i=1;i<=25;i++) r3[i]=r3[i-1]*3;
for(int i=1;i<=18;i++) r5[i]=r5[i-1]*5;
for(int i=1;i<=15;i++) r7[i]=r7[i-1]*7;
for(int i=1;i<=19;i++) r10[i]=r10[i-1]*10;
int n;ll a,b;scanf("%d%lld%lld",&n,&a,&b);
cnt=0;
for(int i=0;i<=35;i++)
for(int j=0;j<=25;j++)
for(int x=0;x<=18;x++)
for(int y=0;y<=15;y++)
{
ll k=r2[i]*r3[j]*r5[x]*r7[y];
if(0<k and k<=ll(n)) g[++cnt]=k;
else break;//剪枝
}
sort(g+1,g+1+cnt);//有序性
f[1][1]=1;
for(int i=1;i<=19;i++)
{
for(int k=1;k<=cnt;k++)
{
if(f[i-1][k]==0) continue;//剪枝
for(int j=1;j<=9;j++)
{
ll ss=ll(g[k])*ll(j);if(ss>ll(n)) break;//剪枝
int pos=lower_bound(g+1,g+1+cnt,int(ss))-g;//其实只是懒得打二分查找
f[i][pos]+=f[i-1][k];
}
}
}
//[a,b)
//[a,b-1]
printf("%lld",dp(b-1,n)-dp(a-1,n));
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/304d.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%