1853: [Scoi2010]幸运数字

Time Limit: 2 Sec  Memory Limit: 64 MB

Submit: 2405  Solved: 887

[][][]

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

【样例输入1】

1 10

【样例输入2】

1234 4321

Sample Output

【样例输出1】

2

【样例输出2】

809

HINT

【数据范围】

对于30%的数据，保证1 < =a < =b < =1000000

对于100%的数据，保证1 < =a < =b < =10000000000

Source

 

思路：

　　挨千刀的搜索题；

　　考试时想到了搜索但是看了复杂度就没去打；

　　结果特么真的是搜索；

　　用搜索实现容斥；

 

来，上代码：

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;long long int l,r,table[40000],num,ans;void pdfs(long long int now){    if(now>r) return ;    table[++num]=now;    pdfs(now*10+6),pdfs(now*10+8);}void pre(){    pdfs(6),pdfs(8);    sort(table+1,table+num+1);    long long new_table[40000],new_num=0;    for(int i=1;i<=num;i++)    {        for(int j=1;j
          
           r) return ;    if(lev) ans+=r/now,ans-=l/now;    else ans-=r/now,ans+=l/now;    for(int i=p;i<=num;i++)    {        double pos=now/gcd(now,table[i]);        if(pos<=r/table[i]) dfs(pos*table[i],i+1,lev^1);    }}int main(){    freopen("luckynumber.in","r",stdin);    freopen("luckynumber.out","w",stdout);    cin>>l>>r;    pre(),l--;    for(int i=1;i<=num;i++) dfs(table[i],i+1,true);    cout<