Luogu P2567 [SCOI2010]幸运数字

题目描述
在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如12，16，666都是“近似幸运号码”。

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

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

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

首先先预处理出所有幸运数字的号码，用dfs实现。

然后将互为倍数的数除去，比如6和66，有了6了就不需要考虑66了

最后剩下943个数，考虑dfs容斥每种情况，因为要计算集合内的lcm，所以这个lcm很快就可以大于r，剪枝即可。

#include<bits/stdc++.h>
#define ll unsigned long long
const int N = 10000;
int tot,n,tag[N];
ll a[N],l,r,ans;
void dfs1(long long x){
    if(x>r) return;
    if(x!=0)
        a[++tot]=x;
    dfs1(x*10+6);
    dfs1(x*10+8);
}
void init(){
    dfs1(0);
    std::sort(a+1,a+1+tot);
    n=std::unique(a+1,a+1+tot)-a-1;
    for(int i=1;i<=n;++i){
        if(tag[i]) continue;
        for(int j=i+1;j<=n;++j){
            if(a[j]%a[i]==0){
                tag[j]=1;
            }
        }
    }
    tot=0;
    for(int i=1;i<=n;++i){
        if(tag[i]) continue;
        a[++tot]=a[i];
    }
    n=tot;
}
ll gcd(ll a,ll b){
    return !b?a:gcd(b,a%b);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
void dfs(int x,int cur,ll s){
    if(s>r) return;
    if(x==n){
        if(s==1) return ;
        if(cur) ans+=r/s-(l-1)/s;
        else ans-=r/s-(l-1)/s;
        return ;
    }
    dfs(x+1,cur^1,lcm(s,a[x+1]));
    dfs(x+1,cur,s);
}
int main(){
    //freopen("luckynumber.in","r",stdin);
    //freopen("luckynumber.out","w",stdout);
    scanf("%lld %lld",&l,&r);
    init();
    dfs(0,0,1);
    printf("%lld\n",ans);
}