BZOJ-1853: [Scoi2010]幸运数字

[文章目录]

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]内,“近似幸运号码”的个数。1 < =a < =b < =10000000000

发现幸运号码在1~10^k内个数的级别是2^k的,所以可以直接dfs预处理出来。1~x内的幸运数字的倍数个数???a1的倍数个数+a2的倍数个数-lcm(a1,a2)的倍数个数……容斥原理。
求lcm的时候好像会爆longlong,long double 转换一下。
容斥的时候好像最后的时候统计答案会快一点(我在口胡不用管我)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3fll;
ll l,r,z[3000];
int top;
void bfs()
{
    z[++top]=6; z[++top]=8;
    int now=1; ll x;
    while(now<=top)
    {
        x=z[now++];
        if(x*10+6<=r) z[++top]=x*10+6;
        if(x*10+8<=r) z[++top]=x*10+8;
    }
}
ll num[3000];
ll ans;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
void dfs(int step,ll now,bool fl)
{
    if(!step)
    {
        if(now!=1) ans=fl?ans-(r/now-l/now):ans+(r/now-l/now);
        return ;
    }
    long double p=(long double)now*z[step]/gcd(now,z[step]);
    if(p<=r) dfs(step-1,p,fl^1);
    dfs(step-1,now,fl);
}
int main()
{
    scanf("%lld%lld",&l,&r); l--; bfs();
    for(int i=1;i<=top;++i)
    {
        for(int j=i+1;j<=top;++j)
            if(z[j]%z[i]==0) z[j]=inf;
    }
    while(z[top]==inf) top--;
    dfs(top,1,1);
    printf("%lld",ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注