AC日记——[SCOI2010]幸运数字 bzoj 1853

1853: [Scoi2010]幸运数字

Time Limit: 2 Sec  Memory Limit: 64 MB
Submit: 2405  Solved: 887
[Submit][Status][Discuss]

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

Day1

 

思路：

　　挨千刀的搜索题；

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

　　结果特么真的是搜索；

　　用搜索实现容斥；

 

来，上代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

long long int l,r,table[],num,ans;

void pdfs(long long int now)

{

    if(now>r) return ;

    table[++num]=now;

    pdfs(now*+),pdfs(now*+);

}

void pre()

{

    pdfs(),pdfs();

    sort(table+,table+num+);

    long long new_table[],new_num=;

    for(int i=;i<=num;i++)

    {

        for(int j=;j<i;j++)

        {

            if(table[j]==) continue;

            if(table[i]%table[j]==)

            {

                table[i]=;

                break;

            }

        }

        if(table[i]) new_table[++new_num]=table[i];

    }

    num=new_num;

    for(int i=;i<=num;i++) table[num-i+]=new_table[i];

    return ;

}

inline long long int gcd(long long int x,long long int y)

{

    return y?gcd(y,x%y):x;

}

void dfs(long long int now,int p,bool lev)

{

    if(now>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+,lev^);

    }

}

int main()

{

    freopen("luckynumber.in","r",stdin);

    freopen("luckynumber.out","w",stdout);

    cin>>l>>r;

    pre(),l--;

    for(int i=;i<=num;i++) dfs(table[i],i+,true);

    cout<<ans;

    fclose(stdin),fclose(stdout);

    return ;

}