[SCOI2010]幸运数字

https://ac.nowcoder.com/acm/problem/20278

题号 NC20278
名称 [SCOI2010]幸运数字
来源 [SCOI2010]

题目描述

在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！

但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。

lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如12，16，666都是“近似幸运号码”。现在lxhgww想知道在一段闭区间[a, b]内，“近似幸运号码”的个数。

样例

输入
1 10
输出
2

输入
1234 4321
输出
809

算法

(dfs + 容斥原理)

~~这道题刚拿到手，感觉就是常规的数位dp...~~

题目给出的幸运数不是常规的6或者8的倍数，而是由6和8组成的数，并且还定义了幸运数的倍数是近似幸运数

那么这道题就不能用数位dp来写，而要找其他方法

题目中提示了幸运数很少10000000000内有2046个

根据近似幸运数的定理，现在我们的目标就是从这些幸运数中挑一些数

求他们的最小公倍数，计算这些最小公倍数的倍数的个数

首先这2046个数字中包含了某些数的倍数如666，是6的倍数

666会在枚举6的倍数的时候被枚举到所以可以删去

最后最多剩下943个数字

计算1~n中x的倍数有多少个可以用n / x来计算

计算[l，r]中x的倍数则可以用容斥原理r / x - ( l - 1) / x来求

不过直接计算会重复统计，所以还需要通过奇加偶减的原则（容斥原理）去重

那么现在的问题就是如何找到所有这些最小公倍数

方法就是dfs

虽然最后剩下的幸运数个数很多，但我们将这些数输出出来发现

位数越多的数个数越多，位数越少的数个数越少（根据乘法原理也很容易理解）

于是我们这样dfs，位数层数u，被选择的幸运数个数cnt，最小公倍数s

将递归的层数 $u$ 表示当前枚举到第 $u$ 个去重后的幸运数

由前面已经选择了的数的最小公倍数计算答案（奇加偶减）

我们枚举这个数选或者不选，
不选，层数+1，被选择的幸运数的个数不变，最小公倍数不变
选，层数+1，被选择的幸运数的个数+1，计算当前数与前面数的最小公倍数

由于位数越多的数个数越多，位数越少的数个数越少我们加入一个剪枝

当最小公倍数大于r时直接返回

像是8888888866这样的幸运数，递归两层后就直接反回了

这样的数还有很多所以dfs实际递归次数很少

这里还有一个剪枝，需要将幸运数按照从大到小的顺序排序再进行dfs不然会超时

如果小的数字在高层那么需要递归较深才会被”最小公倍数大于r返回“的剪枝剪掉

如果大的数字在高层那么需要递归一两次就会被剪枝

时间复杂度

参考文献https://blog.nowcoder.net/n/c9b403ebf6284dbcaaa45f0bc54d18c3

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
const LL N = 10000000000ll;
vector<LL> nums,num;
LL l,r;
LL n;
LL ans;

void dfs(LL s)
{
    if(s > r) return;
    if(s != 0) nums.push_back(s);
    dfs(s * 10 + 6);
    dfs(s * 10 + 8);
}

bool cmp(LL &a,LL &b)
{
    return a > b;
}

void init()
{
    dfs(0ll);
    for(int i = 0;i < nums.size();i ++)
    {
        bool flag = true;
        for(int j = 0;j < nums.size();j ++)
        {
            if(i == j) continue;
            if(nums[i] % nums[j] == 0) flag = false;
        }
        if(flag) num.push_back(nums[i]);
    }
    sort(num.begin(),num.end(),cmp);
}

LL calc(LL x)
{
    return r / x - (l - 1) / x;
}

void dfs1(int u,int cnt,LL s)
{
    if(s > r) return;
    if(u >= num.size())
    {
        if(cnt != 0)
        {
            if(cnt & 1) ans += calc(s);
            else ans -= calc(s);
        }
        return;
    }
    dfs1(u + 1,cnt,s);
    LL lcm = s / __gcd(s,num[u]);
    if(lcm <= r / num[u]) dfs1(u + 1,cnt + 1,lcm * num[u]);
}

void solve()
{
    scanf("%lld%lld",&l,&r);
    init();
    dfs1(0,0,1ll);
    printf("%lld\n",ans);
}

int main()
{
    /*#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #else
    #endif // LOCAL*/
    int T = 1;
    // init();
    // scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}