先预处理$[1,10^{10}]$内的所有幸运号码。

对于一个幸运号码$X$，在$[A,B]$中$X$的倍数的个数，就是

$\lfloor\frac{B}{X}\rfloor-\lceil\frac{A}{X}\rceil+1$。

然而，两个幸运号码对应的近似幸运号码可能有交集。考虑到这一点，就可以用容斥，也就是：

选$1$个幸运号码$-$选$2$个幸运号码的lcm$+$选$3$个幸运号码的lcm$-...$

但是直接做是$2^{2046}$的，啃腚会TLE。考虑$3$个剪枝：

1、发现对于两个幸运号码$a,b$，如果$a|b$，那么对于所有的$b|x$就一定有$a|x$，因此这样的$b$是不必要的。去掉所有这样的$b$后，还剩下$943$个幸运号码。 2、当前的lcm一旦大于$B$就不再继续搜索。这样复杂度就能大大降低。

3、将预处理出的幸运号码从大到小排序，使lcm能更快地超越上界$B$。

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e4 + 5;
ll A, B, a[N], num[N], Ans;
int tot, n; bool mark[N];
void dfs1(int dep, int cnt, ll now, ll x) {
    if (dep > cnt) return (void) (a[++tot] = now);
    dfs1(dep + 1, cnt, now + x * 6, x * 10);
    dfs1(dep + 1, cnt, now + x * 8, x * 10);
}
void sieve() {
    int i, j;
    for (i = 1; i <= tot; i++) {
        if (!mark[i]) num[++n] = a[i];
        for (j = i + 1; j <= tot; j++)
            if (a[j] % a[i] == 0) mark[j] = 1;
    }
}
ll Cnt(ll l, ll r, ll PYZ) {
    l = l / PYZ + (l % PYZ != 0); r /= PYZ;
    return r - l + 1;
}
void dfs2(int dep, int cnt, ll val) {
    if (val > B) return;
    if (dep > n) {
        if (cnt == 0) return;
        Ans += Cnt(A, B, val) * ((cnt & 1) ? 1 : -1);
        return;
    }
    dfs2(dep + 1, cnt, val);
    ll tmp = val / __gcd(val, num[dep]);
    if (1.0 * tmp * num[dep] <= B)
        dfs2(dep + 1, cnt + 1, tmp * num[dep]);
}
bool comp(ll a, ll b) {return a > b;}
int main() {
    int i; cin >> A >> B;
    for (i = 1; i <= 10; i++) dfs1(1, i, 0, 1);
    sieve(); sort(num + 1, num + n + 1, comp);
    cout << (dfs2(1, 0, 1), Ans) << endl;
    return 0;
}

关于更多分块打表的内容，可以参见我写的日报 浅谈打表与其技巧

分块打表如闪电般的啪的一下就过了，很快啊！

这题还不用卡表长，真是分块打表好的入门题（

先 dfs 出所有的幸运数字，发现只有 2046 个。

void dfs(ll d)
{
	if(d>up) return;
	if(d) a[++cnt]=d;
	dfs(d*10+6),dfs(d*10+8);
}

然后我们需要设计出一个函数他支持求 $[l,r]$ 中近似幸运数字的个数

枚举幸运数字，利用类似埃筛和 P1835 的做法筛出来。

$10^{10}$ 的数据范围的话，表长选 $b=2\times 10^6$ 差不多。

int ask(ll l,ll r)
{
	int i,s=0;
	memset(t,0,sizeof(t));
	for(i=1;i<=cnt;i++)
		for(ll p=a[i],j=r/p*p;j>=l;j-=p)
			t[j-l]=1;
	for(ll j=l;j<=r;j++)
		s+=t[j-l];
	return s;
}

然后就可以利用这个函数进行打表：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[100005];
int cnt;
const ll up=1e10;
void dfs(ll d)
{
	if(d>up) return;
	if(d) a[++cnt]=d;
	dfs(d*10+6),dfs(d*10+8);
}
const int bl=2e6;
bool t[bl+5];
int ask(ll l,ll r)
{
	int i,s=0;
	memset(t,0,sizeof(t));
	for(i=1;i<=cnt;i++)
		for(ll p=a[i],j=r/p*p;j>=l;j-=p)
			t[j-l]=1;
	for(ll j=l;j<=r;j++)
		s+=t[j-l];
	return s;
}
signed main()
{
	freopen("out","w",stdout);
   dfs(0);
    ll i,j,l,r;
    for(i=0;i+bl<=up;i+=bl)
    {
    	l=i+1,r=i+bl;
    	printf("%d,",ask(l,r));
	}
}

跑了 8s 就出来了，很快啊！

最后还可以利用这个函数做最终的提交程序：https://www.luogu.com.cn/paste/c1lr3rkh