[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]内，“近似幸运号码”的个数。

题解：

容斥原理。首先预处理出幸运号码（只含数字6、8的那些），再把其中是其它幸运号码倍数的筛掉，然后容斥解决倍数的那些就好了。有个问题是运算过程中会爆long long，需要用到double，然后SB的我把 (double)t∗list[x] 写成了 (double)(t∗list[x]) ，于是TLE了3次……

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
int len=-;
bool mark[];
LL list[];
LL l,r;
void pre(LL x)
{
    if(x>r)return;
    list[++len]=x;
    pre(x*+);pre(x*+);
}
LL ans=;
LL gcd(LL a,LL b)
{
    if(b==)return a;
    return gcd(b,a%b);
}
void dfs(int ch,LL now,int x)
{
//  printf("%d %lld %d\n",ch,now,x);
    if(x==len+)
    {
        if(!ch)return;
        if(ch&)ans+=(r/now-(l-)/now);
        else ans-=(r/now-(l-)/now);
        return;
    }
    dfs(ch,now,x+);
    LL t=now/gcd(now,list[x]);
    if((double)t*list[x]<=r)dfs(ch+,t*list[x],x+);
}
bool cmp(LL x,LL y){return x>y;}
int main()
{
    memset(mark,false,sizeof(mark));
    scanf("%lld%lld",&l,&r);
    pre();
    sort(list+,list++len);
    for(int i=;i<len;i++)
    {
        if(!mark[i])
        {
            for(int j=i+;j<=len;j++)
            if(list[j]%list[i]==)mark[j]=true;
        }
    }
    int Len=len;len=;
    for(int i=;i<=Len;i++)
    if(!mark[i])list[++len]=list[i];
    sort(list+,list++len,cmp);    //for(int i=1;i<=len;i++)printf("%lld ",list[i]);
    dfs(,,);
    printf("%lld",ans);
}