幸运数字(bzoj 1853)

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

/*

    容斥原理。

    先求出范围内所有的幸运数字，然后筛它们的倍数，直接O(n)筛很明显会超时，直接求的话可能会一个数被统计多次，

    这样就用到了容斥原理。

    先考虑只有6和8的情况，答案为lim/6+lim/8-lim/lcm(6,8)。

    当数字变多时，我们会发现加上的都是奇数集合的贡献，减去的都是偶数集合的贡献，dfs即可。

    有一个需要注意的地方，算lcm的时候会爆long long，要用double。

*/

#include<iostream>

#include<cstdio>

#include<algorithm>

#define N 10010

#define lon long long

using namespace std;

lon l,r,a[N],b[N],n,m,ans;

bool vis[N];

void init(lon x){

    if(x>r) return;

    if(x) a[++m]=x;

    init(x*+);

    init(x*+);

}

lon gcd(lon x,lon y){

    if(!y) return x;

    return gcd(y,x%y);

}

void dfs(int x,int y,lon z){

    if(x>n){

        if(y&) ans+=r/z-(l-)/z;

        else if(y) ans-=r/z-(l-)/z;

        return;

    }

    dfs(x+,y,z);

    lon tmp=z/gcd(z,a[x]);

    if((double)tmp*a[x]<=r)

        dfs(x+,y+,tmp*a[x]);

}

int main(){

    cin>>l>>r;

    init();

    sort(a+,a+m+);

    for(int i=;i<=m;i++){

        if(!vis[i]) b[++n]=a[i];

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

            if(a[j]%a[i]==) vis[j]=;

    }

    for(int i=;i<=n;i++) a[n-i+]=b[i];

    dfs(,,);

    cout<<ans;

    return ;

}