Description

在中国, 很多人都把 \(6\) 和 \(8\) 视为是幸运数字! lxhgww 也这样认为, 于是他定义自己的 “幸运号码” 是十进制表示中只包含数字 \(6\) 和 \(8\) 的那些号码, 比如 \(68, 666, 888\) 都是 “幸运号码”! 但是这种 “幸运号码” 总是太少了, 比如在 \([1, 100]\) 的区间内就只有 \(6\) 个\((6, 8, 66, 68, 86, 88)\), 于是他又定义了一种 “近似幸运号码”. lxhgww 规定, 凡是 “幸运号码” 的倍数都是 “近似幸运号码”, 当然, 任何的 “幸运号码” 也都是 “近似幸运号码”, 比如 \(12, 16, 666\) 都是 “近似幸运号码”. 现在 lxhgww 想知道在一段闭区间 \([a, b]\) 内, “近似幸运号码” 的个数.

Input

输入数据是一行, 包括 \(2\) 个数字 \(a\) 和 \(b\)

Output

输出数据是一行, 包括 \(1\) 个数字, 表示在闭区间 \([a, b]\) 内 “近似幸运号码” 的个数

Sample Input

1234 4321

Sample Output

809

Data Range

对于 30% 的数据, 保证 \(1 \leq a \leq b \leq 10^6\)

对于 100% 的数据, 保证 \(1 \leq a \leq b \leq 10^{10}\)

Explanation

首先我们可以枚举出来所有的幸运数字对吧~ 这个复杂度应该是 \(O(2^{\log_{10} b})\) 的, 然后我们 再为了逐个考虑它们的重复性, 需要排除互相是倍数的情况, 这样如果效率比较低有可能 会写到 \(O(2^{2 \cdot \log_{10} b})\) 的复杂度, 不过没有什么影响.

个人大概测了一下, 不重复的幸运数字大概在 \(500\) 个以内. 这样的题目当然非容斥原理 莫属了! 但是 \(2^{500}\) 的复杂度不会超时吗? 不会 (如果你不优化, 会).

这样, 直接上来瞎搞 DFS, 然后遇到乘积只要变得足够大 (\(\geq b\)) 的情况下, 就剪枝.

发现这样速度还是不够怎么办呢? 把数值大的放到前面先递归, 这样得到的性能会上百倍地 好于从小到大地递归 (原因就是, 大的可能再后边被算了多次, 而且对结果没有什么贡献, 所以才先选后面的来优化).

然后瞎搞一发就可以 AC 了 (第一次交上去 WA 的原因是把 \(a, b\) 开成了 int)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
typedef double llf;
const int maxn = 2048;

lli gcd(lli a, lli b) {
    if (b == 0) return a;
    return gcd(b, a % b); }

lli n, a, b, n_srt;
lli arr[maxn], arr_srt[maxn];
lli res = 0;

void make_lucky_arr(lli last_val)
{
    if (last_val > b)
        return ;
    if (last_val > 0)
        arr_srt[++n_srt] = last_val;
    make_lucky_arr(last_val * 10 + 6);
    make_lucky_arr(last_val * 10 + 8);
    return ;
}

void dfs(int pos, int selected, lli product)
{
    if (pos > n) {
        if (selected & 1)
            res += b / product - (a - 1) / product;
        else if (selected)
            res -= b / product - (a - 1) / product;
        return ;
    }
    dfs(pos + 1, selected, product);
    lli tmp = product / gcd(arr[pos], product);
    // This place needs extra precaution in case product exceeds 2^63-1
    if ((llf)arr[pos] * tmp <= b)
        dfs(pos + 1, selected + 1, arr[pos] * tmp);
    return ;
}

int main(int argc, char** argv)
{
    scanf("%lld%lld", &a, &b);
    // Generating basic lucky numbers
    n_srt = n = 0;
    make_lucky_arr(0);
    sort(arr_srt + 1, arr_srt + 1 + n_srt);
    // Pruning duplicate / duplications
    for (int i = 1; i <= n_srt; i++) {
        bool is_duplicate = false;
        for (int j = 1; j <= n; j++)
            if (arr_srt[i] % arr[j] == 0) {
                is_duplicate = true;
                break;
            }
        if (is_duplicate)
            continue;
        arr[++n] = arr_srt[i];
    }
    sort(arr + 1, arr + 1 + n); // Precaution.
    // Using this could **dramatically** increase the speed by reducing the
    // span of tree leaves...
    for (int i = 1; i * 2 <= n; i++)
        swap(arr[i], arr[n + 1 - i]);
    // Evaluating result
    dfs(1, 0, 1);
    printf("%lld\n", res);
    return 0;
}