描述

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

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

lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如12，16，666都是“近似幸运号码”。

现在lxhgww想知道在一段闭区间[a, b]内，“近似幸运号码”的个数。

输入

输入数据是一行，包括2个数字a和b

输出

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

样例输入[复制]

1 10

【样例输入2】

1234 4321

【样例输出2】

809

样例输出[复制]

2

提示

【数据范围】 对于30%的数据，保证1<=a<=b<=1000000 对于100%的数据，保证1<=a<=b<=10000000000

标签

scoi2010省选

 

 

 

 

还好看出来了这是一道容斥原理的题目，但是有一个问题是我们要容斥哪些元素

对于10^10来说有10位，所以我们实际上就在十个数字上面选择是6还是8，这些数字都是幸运数字（不是近似的）

所以实际上所有的幸运数字应该有2047个

但是我们在筛选的时候肯定不能直接容斥原理因为复杂度可以达到2

²⁰⁴⁷，直接爆了啊

我们发现如果一个幸运数字是另一个的倍数那么这个幸运数字实际上是没有意义的

所以我们就预处理一下，处理真幸运数字的时候我们就直接枚举每一位上面的可能性就可以了

去重也很简单，复杂度可以忽略不计

接着就是搜索

我们发现在验证是否是大于右边界的时候会爆long long，所以我们要用double来进行验证

最重要的是乘法的时候要尽量分开写才能保证double比较的时候准确

总结了一下实际上我们的容斥原理的代码无非就是这样：

1 void dfs(int dep,int use,int now){ 2     if(dep>总值){ 3         if(!use)return; 4         if(use%2)ans+; 5         else ans- ; 6         return ; 7     }  8     //不选这个数字  9     dfs(dep+1,use,now);10     //选择这个数字11     if(...

那么这道题实际上就是一个道理

code：

1 #include
      
        2 #include
       
         3 #include
        
          4 #define ll long long 5 #include
         
           6 #include
          
            7 using namespace std; 8 ll a,b,ans; 9 long long tot,tot_,p[5000],check[5000],num[5000];10 inline ll gcd(ll a,ll b){11     if(a
           
            cnt){ //预处理的过程 20 p[++tot_]=now;21 return;22 }23 pre(dep+1,cnt,now+x*8,x*10);24 pre(dep+1,cnt,now+x*6,x*10);25 }26 inline void uniq(){ //去重的过程，就像自带的函数unique一样 27 for(long long i=1;i<=tot_;i++){28 for(long long j=1;j
            
             b)return;//如果当前数字比右边界还要大就直接剪枝 38 if(pos>tot){ //如果搜到了大于tot的地方 ，也就是我们枚举完了所有数字 39 if(!k)return;//一个数字都没有就是0，肯定是没有什么意义的 （与上一道一样会让答案不准确） 40 if(k&1)ans+=b/x-a/x;//如果是奇数个数字组成的数字那么就要加上去 41 else ans-=b/x-a/x;//如果是偶数个就要减掉 42 return;43 }44 dfs(pos+1,k,x);//如果这一位不搜索 45 ll tmp=x/gcd(x,num[pos]);//这一步是非常非常重要的，这可以决定你是否tle，注意在大数运算的时候要尽量分开进行运算，这样后面的double运算才准确 46 if((double)1.0*tmp*num[pos]>(double)b)return;//如果他们的最小的公倍数都超过了右边界，就要直接剪枝掉 47 dfs(pos+1,k+1,lcm(x,num[pos]));//乘上这个数字直接往下走 48 }49 int main(){50 cin>>a>>b;51 for(long long i=1;i<=10;i++)pre(1,i,0,1);52 uniq();53 for(long long i=tot_;i>=1;i--)if(!check[i])num[++tot]=p[i];54 a--;55 dfs(1,0,1);56 cout<