学了一种爆搜版+剪枝的容斥方法，即类似数位dp时按位进行容斥，同时需要在搜索过程中进行剪枝
/* 容斥原理，先在打出的表里筛掉所有倍数，然后用容斥原理+1个的倍数-2个lcm的倍数+3个lcm的倍数... 注意剪枝，判断防止爆long long */ #include<bits/stdc++.h> using namespace std; #define ll long long #define maxn 200005 ll l,r,ans; ll a[maxn],m,b[maxn],n; void init(ll x){ if(x>r)return; a[++m]=x; init(x*10+6); init(x*10+8); } void dfs(int pos,int num,ll now){ if(pos>n){ if(num%2) ans+=r/now-(l-1)/now; else if(num)ans-=r/now-(l-1)/now; return; } dfs(pos+1,num,now);//不取第pos位 ll tmp=now/__gcd(b[pos],now);//防止爆ll if((double)b[pos]*tmp<=(double)r) dfs(pos+1,num+1,b[pos]*tmp); } int vis[maxn]; int main(){ cin>>l>>r; init(6);init(8); sort(a+1,a+1+m);//排成有序数列 for(int i=1;i<=m;i++) if(vis[i]==0){ for(int j=i+1;j<=m;j++) if(a[j]%a[i]==0) vis[j]=1; } for(int i=m;i>=1;i--) if(!vis[i])b[++n]=a[i]; dfs(1,0,1); cout<<ans<<endl; }