幸运数字

Posted on Edited on In

题目大意:定义幸运数字为只包含6,8的数字,扩展定义"近似幸运数字"为:是"幸运数字"的倍数都是"近似幸运数字".求一个区间内幸运数字的个数.

正解貌似是数位dp,但是没有题解介绍这个,大多都是搜索剪枝.

首先预处理出来范围内的幸运数字

然后考虑一个显然的性质:\(\dfrac B x - \dfrac A x\)是\([A,B]\)中x的倍数的个数.

但是考虑到有交集,所以选择容斥一下:

选1个幸运数字-选2个幸运数字的lcm+选3个幸运数字的lcm

然后剪枝,减掉了好多好多状态:

  • 对于一个数字a,和b如果发现b是a的倍数,那么对于所有的为b的倍数的数字,一定是a的倍数,所以这样的b就无用了.

  • 当前lcm大于B就stop

  • 倒序排序,方便更快超越上限(常用技巧)

代码如下:

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e4 + 66;

ll a, b, res, num[N], nam[N];
int cnt, vis[N];

inline void pres_dou(int now, ll sum)
{
    if (sum > b) return;
    if (sum != 0) num[++ cnt] = sum;
    if (now > 10) return;
    pres_dou(now + 1, sum * 10 + 6), pres_dou(now + 1, sum * 10 + 8);
    return;
}

inline void yhm_cut()
{
    int i, j, ret(0);
    for (i = 1; i <= cnt; ++ i)
    {
        if (vis[i]) continue;
        if (num[i] <= b / 2) nam[++ ret] = num[i];
        else res += b / num[i] - a / num[i];
        for (j = i + 1; j <= cnt; ++ j) if (num[j] % num[i] == 0) vis[j] = 1;
    }
    return (void)(cnt = ret);
}

inline int cmp(int x, int y) {return x > y;}

inline void dfs(int now, ll sum, int t)
{
    if (sum > b) return;
    if (now > cnt) return (void)((sum == 1) ? a = a : (res += (b / sum - a / sum) * ((t & 1) ? 1 : -1)));
    dfs(now + 1, sum, t);
    ll tmp = nam[now] / __gcd(nam[now], sum);
    if (tmp * sum <= b) dfs(now + 1, tmp * sum, t + 1);
    return;
}

signed main()
{	
    a = read(), b = read(), -- a;
    pres_dou(1, 0), sort(num + 1, num + 1 + cnt);
    yhm_cut(), sort(nam + 1, nam + 1 + cnt, cmp);
    dfs(1, 1, 0), put(res);

    return 0;
}

后记:

学好搜索,打遍天下无敌手...