思路

本来以为是数位,想不出状态,后来又想着容斥一下以为都是的倍数的数量+的数量-的数量,然后就死了.万万没想到是.

思路很简单,就是先爆搜出那些合法的数/基数,其他数一定是这些数的倍数,然后把爆搜的数去个重,有些数是里面数的倍数,然后从小到大排序一下(剪枝).然后再用容斥原理统计答案即可.

坑点

题目给的是不是会爆,同时很多数据都需要开,建议都开下= - =

code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l,r,n;
vector<ll>num;
vector<ll>Num;
void DFS(ll u)
{
    if(u>r) return;
    if(u)   num.push_back(u);
    DFS(u*10+6);
    DFS(u*10+8);
}

bool cmp(ll a,ll b)
{
    return a>b;
}

void init()
{
    DFS(0ll);
    sort(num.begin(),num.end());
    int sz=num.size();
    for(int i=0;i<sz;i++)
    {
        bool flag=true;
        for(int j=0;j<i;j++)
        {
            if(num[i]%num[j]==0)    flag=false;
        }
        if(flag)    Num.push_back(num[i]);
    }
    sort(Num.begin(),Num.end(),cmp);
    n=Num.size();
}

ll Ans(ll u)
{
    return r/u-(l-1)/u;
}

ll dfs(int dep,int cnt,ll now)
{
    ll res=0;
    if(now>r)   return res;
    if(dep==n)
    {
        if(cnt==0)  return res;
        if(cnt&1)   res+=Ans(now);//+
        else        res-=Ans(now);//-
        return res;
    }
    res+=dfs(dep+1,cnt,now);
    ll sb=(now)/__gcd(now,Num[dep]);
    if(1.0*sb*Num[dep]<=r)    res+=dfs(dep+1,cnt+1,sb*Num[dep]);
    return res;
}

int main()
{
    cin>>l>>r;
    init();
    cout<<dfs(0,0,1ll)<<'\n';
    return 0;
}