题意：

所有只含6与8的数叫做幸运数字，幸运数字的倍数叫做近似幸运数字，幸运数字都是近似幸运数字。 给定区间[l,r]求其中近似幸运数字个数。
1 < =l< =r< =10000000000

思路：

类似以前做的能被3，5，7整除的数呀什么的。

首处理出所有的幸运数字， 然后找到这些数中的”幸运素数”(就是这些数组成的序列中不能被其他元素整除的数）。

找到这些数,那么 其实就把这个问题就是成求[a,b]内那些”幸运素数”的倍数有多少个就好了。

ans=[x/一个幸运素数的最小公倍数]−[x/两个幸运素数的最小公倍数]+[x/三个幸运素数的最小公倍数]−….

然后dfs一下就可以了。

这里有一个问题，因为这里如果lcm>r的话就可以不再处理了，在dfs之前要把所有幸运素数从大到小排列，这是一个很重要的剪枝，可以减少回溯的次数。

此外，在中间判断lcm是否大于r的时候会爆long long，所以用double来判断。

如果要再快一点的话可以直接把幸运素数都直接打表打出来（doge.jpg

还有一个可以剪枝，每个大于上界/2的数字，倍数肯定是会超上界的，所以这里就直接加在ans，就可以少一些计算。

代码：

typedef long long ll;
int num;
ll a[2100];
bool vis[2100];
ll l,r;
ll ans;
bool cmp(ll x,ll y)
{
    return x>y;
}
ll gcd(ll a,ll b)
{
    if(a<b){ll temp;temp=a;a=b;b=temp;}
    while(a%b){ll r=a%b;a=b;b=r;}
    return b;
}
void init(ll x)
{
    if(x>r)return;
    if(x!=0)a[num++]=x;
    init(x*10+6);
    init(x*10+8);
}
void dfs(int pos,int tot,ll lcm)
{
    if(pos==num)
    {
        //printf("tot=%d lcm=%lld",tot,lcm);
        if(tot!=0&&tot%2==0)ans-=r/lcm-(l-1)/lcm;//这里注意和(r-l+1)/lcm是不同的
        else if(tot!=0)ans+=r/lcm-(l-1)/lcm;
        //printf("(%lld)\n",(r-l+1)/lcm);
        return;
    }
    dfs(pos+1,tot,lcm);
    if((double)(lcm/gcd(lcm,a[pos]))*a[pos]<=r)//long long会爆
        dfs(pos+1,tot+1,lcm/gcd(lcm,a[pos])*a[pos]);
}
int main()
{
    scanf("%lld%lld",&l,&r);
    num=0;
    init(0);
    sort(a,a+num);
    memset(vis,0,sizeof(vis));
    for(int i=num-1;i>=0;i--)
    {
        if(!vis[i])//不是某个数的倍数
        {
            for(int j=i-1;j>=0;j--)
            {
                if(a[i]%a[j]==0)
                    vis[i]=true;
            }
        }
    }
    int tot=0;
    for(int i=0;i<num;i++)
    {
        if(!vis[i])
            a[tot++]=a[i];
    }
    num=tot;
    sort(a,a+num,cmp);//剪枝
    //printf("%d\n",num);
    /*for(int i=0;i<num;i++)
        printf("%lld ",a[i]);
    printf("\n");*/
    ans=0;
    dfs(0,0,1);
    printf("%lld\n",ans);
    return 0;
}