[文章目录]
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;
}