题目中询问数据范围达到了1e10，且要求找符合要求数的个数，很容易让我想到数位dp，但其实每必要，发现幸运数字只有 \(2^{10}\) 个，答案就是近似幸运数+幸运数-两者交集，考虑容斥，每个 \([l,r]\) 之间的可能被之前的幸运数更新多次，通过容斥，很容易知道1个幸运数个数-2个幸运数lcm个数+3个幸运数lcm个数...dfs实现，但显然会T，考虑优化，一个幸运数是之前的幸运数倍数，就没必要对他dfs了；还有，因为lcm>qr时就可以退出了，所以我们的数越大，lcm增加的就越快，dfs递归次数就会越少（最好卡常会更快）
计算 \([l,r]\) 间 \(X\) 倍数的个数，就是 \(floor(R/x)-ceil(L/x)+1\) 个
#include<bits/stdc++.h>
#define int __int128
using namespace std;
const int N=2e6+5;
int ql,qr,S1[N],cnt=0;
vector<int> E;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)
+fread(buf,1,100000, stdin),p1==p2)?EOF:*p1++;
}
template<typename T>inline
void read(T& x){
T f=1,b=0;char ch=gc();
while (ch<'0'||ch>'9') {
if(ch=='-')f=-1;
ch=gc();
}
while(ch>='0'&&ch<='9')
b*=10,b+=ch-'0',ch=gc();
x=f*b;return;
}
template<typename T> inline
void print(T x){
if(x==0)return putchar('0'),void();
if(x<0)putchar('-'),x=-x;
int st[129]={0},k=0;
while(x)st[++k]=x%10,x/=10;
for(int i=k;i;i--)putchar(st[i]+'0');
}
void dfs(int len,int x){
if(x<=qr&&x){
E.emplace_back(x);
}
if(x>qr)return;
dfs(len+1,x*10+8);
dfs(len+1,x*10+6);
return;
}
bool vis[N];
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
int lcm(int a,int b){
return a/gcd(a,b)*b;
}
int ans=0;
void dfs2(int len,int tmp,int sign){
if(tmp>qr)return;
if(len==cnt+1){
if(!tmp)return;
int tot=floor(qr*1.0/tmp)-ceil(ql*1.0/tmp)+1;
ans=ans+sign*tot;
return;
}
int ntmp;
if(!tmp)ntmp=S1[len];
else ntmp=lcm(tmp,S1[len]);
dfs2(len+1,ntmp,-sign);
dfs2(len+1,tmp,sign);
return;
}
bool cmp(int a,int b){
return a>b;
}
signed main(){
read(ql),read(qr);
dfs(0,0);
sort(E.begin(),E.end());
for(int i=0;i<E.size();i++){
if(vis[i])continue;
S1[++cnt]=E[i];
for(int j=i+1;j<E.size();j++){
if(E[j]%E[i]==0)vis[j]=true;
}
}
sort(S1+1,S1+cnt+1,cmp);
dfs2(1,0,-1);
print(ans),puts("");
return 0;
}