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=-
1;
bool mark[
10000];
LL
list[
10000];
LL l,r;
void pre(LL x)
{
if(x>r)
return;
list[++len]=x;
pre(x*
10+
6);pre(x*
10+
8);
}
LL ans=
0;
LL gcd(LL a,LL b)
{
if(b==
0)
return a;
return gcd(b,a%b);
}
void dfs(
int ch,LL now,
int x)
{
if(x==len+
1)
{
if(!ch)
return;
if(ch&
1)ans+=(r/now-(l-
1)/now);
else ans-=(r/now-(l-
1)/now);
return;
}
dfs(ch,now,x+
1);
LL t=now/gcd(now,
list[x]);
if((
double)t*
list[x]<=r)dfs(ch+
1,t*
list[x],x+
1);
}
bool cmp(LL x,LL y){
return x>y;}
int main()
{
memset(mark,
false,
sizeof(mark));
scanf(
"%lld%lld",&l,&r);
pre(
0);
sort(
list+
1,
list+
1+len);
for(
int i=
1;i<len;i++)
{
if(!mark[i])
{
for(
int j=i+
1;j<=len;j++)
if(
list[j]%
list[i]==
0)mark[j]=
true;
}
}
int Len=len;len=
0;
for(
int i=
1;i<=Len;i++)
if(!mark[i])
list[++len]=
list[i];
sort(
list+
1,
list+
1+len,cmp);
dfs(
0,
1,
1);
printf(
"%lld",ans);
}
