[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);
}