做法：dfs+容斥

思路

  • 先找出只含6和8的数，再把那些成倍数关系的给删了

  • 我们知道对于一个幸运号码x，在[l,r]中x的倍数的个数，就是

  • 之后根据容斥（奇加偶减）,答案为选1个幸运号码−选2个幸运号码的lcm+选3个幸运号码的lcm...

  • 注意:

1.在求lcm的时候会爆long long，可以转化成long double
2.找出那些不成倍数关系的幸运号码的时候要用从大到小排序，否则会T（我也不知道是什么玄学）

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=100010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

ll l,r,ans;
set<ll> s;
vector<ll> g;

void dfs(ll n){
    if(n*10+6<=r) s.insert(n*10+6),dfs(n*10+6);
    if(n*10+8<=r) s.insert(n*10+8),dfs(n*10+8);
}

void dfs2(int dep,int cnt,ll val){
    if(val>r) return;
    if(dep==g.size()){
        if(cnt) ans+=(r/val-(l+val-1)/val+1)*((cnt&1)?1:-1);
        return;
    }
    dfs2(dep+1,cnt,val);    
    ld temp=1.0*val/__gcd(val,g[dep])*g[dep];
    if(temp<=r) dfs2(dep+1,cnt+1,temp);
}

void solve(){
    cin>>l>>r;
    dfs(0);
    for(auto x:s){
        bool flag=1;
        for(auto y:g){
            if(x%y==0){
                flag=0;
                break;
            }
        }
        if(flag) g.pb(x);
    }
    reverse(g.begin(),g.end());
    dfs2(0,0,1);
    cout<<ans<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}