Mayflyyh
Mayflyyh
MayFlyyh's Blog
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);
}
本文链接:http://www.mayflyyh.com/archives/444
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      容斥      Luogu P2567 [SCOI2010]幸运数字
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

Luogu P2567 [SCOI2010]幸运数字
题目描述 在中国,很多人都把6和8视为是幸运数字!lxhgww也这样认为,于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码,比如68,666,888都是“幸运号码”!但是这种“…
扫描二维码继续阅读
2018-12-19