HYSBZ-1853 幸运数字(容斥原理，dfs)

迈不过友情╰ 2022-06-09 04:52 183阅读 0赞

## 幸运数字 ##

在中国，很多人都把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  
【样例输入1】  
1 10  
【样例输入2】  
1234 4321  
Sample Output  
【样例输出1】  
2  
【样例输出2】  
809  
Hint  
【数据范围】  
对于30%的数据，保证1 < =a < =b < =1000000  
对于100%的数据，保证1 < =a < =b < =10000000000

思路：这道题就是一道容斥原理的题目，我们可以先把所有的幸运数字打个表（大约2000个数），然后再把其中值是之前的幸运数字的倍数的幸运数字给去掉，剩下的就是需要进行容斥的表（由表可知有943个数）。然后我们再根据b确定所需要使用的表的范围，并把这个范围内的幸运数字从大到小排列，这是为了在dfs的时候能更快的剪掉大枝，之后就可以开始dfs了，奇加偶减。需要注意的是这道题可能会爆long long，所以中途要用double来转换一下。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cstdlib>
    #include <cmath>
    #include <vector>
    #include <queue>
    #include <map>
    #include <algorithm>
    #include <set>
    #include <functional>
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    const int INF = 1e9 + 5;
    const int MAXN = 305;
    const int MOD = 10007;
    const double eps = 1e-8;
    const double PI = acos(-1.0);
    
    LL lucky[3000];
    LL luc[3000];
    LL ans;
    int ss;//表示有多少个幸运数字在范围内
    
    void init1()//打幸运数字的表
    {
        int step1, step2;
        step1 = 0;
        step2 = 1;
        memset(lucky, 0, sizeof lucky);
        lucky[0] = 0;
        for (int i = 1; i <= 10; i++)
            for (int k = 1; k <= pow(2, i - 1); k++, step1++)
            {
                lucky[step2] = lucky[step1] * 10 + 6;
                step2++;
                lucky[step2] = lucky[step1] * 10 + 8;
                step2++;
            }
    }
    void init2()//打出没有倍数关系的幸运数字的表
    {
        memset(luc, 0, sizeof luc);
        int flag;
        int step = 0;
        for (int i = 1; i < 2100; i++)
        {
            flag = true;
            for (int j = 1; j < i; j++)
                if (lucky[i] % lucky[j] == 0)
                {
                    flag = false;
                    break;
                }
            if (flag)
                luc[++step] = lucky[i];
        }
    }
    LL gcd(LL a, LL b)
    {
        return b == 0 ? a : gcd(b, a%b);
    }
    
    void dfs(int num, LL LCM, int flag/*奇加偶减*/, LL a, LL b, int first/*是否是第一个选的数*/)
    {
        if (num == ss || LCM>a)
        {
            if (LCM == 1)//如果一个数都没有选
                return;
            if (flag)
                ans -= a / LCM - b / LCM;
            else
                ans += a / LCM - b / LCM;
            return;
        }
        dfs(num + 1, LCM, flag, a, b, first);
        double t;
        if (first == 0)
            t = luc[num];
        else
            t = (double)LCM*luc[num] / (double)gcd(luc[num], LCM);
        if (t <= a)
            dfs(num + 1, (LL)t, flag ^ 1, a, b, 1);
    }
    
    LL solve(LL m, LL n)
    {
        ans = 0;
        dfs(1, 1, 1, m, n, 0);
        return ans;
    }
    
    bool cmp(LL a, LL b)
    {
        return a > b;
    }
    
    void tt(LL b)//从大到小排列所需范围内的幸运数字
    {
        for (ss = 1; ss <= 943; ss++)
            if (luc[ss] > b)
                break;
        sort(luc + 1, luc + ss, cmp);
    }
    
    int main()
    {
        init1();
        init2();
        LL a, b;
        int i;
        while (scanf("%lld%lld", &a, &b) != EOF)
        {
            tt(b);
            printf("%lld\n", solve(b, a - 1));
        }
    }