翻了一些blog，只有我用状压预处理嘛2333，。把二进制位的0当成6，1当成8就行啦。(2393是2和9
然后\( dfs \)容斥，加上一个数的\( lcm \)，减去两个数的\( lcm \)，加上三个数的\( lcm \)...需要一些剪枝来控制复杂度。
剪枝：
1.对于预处理出来的幸运数字，把倍数都去掉
2.当\( lcm>b \)时退出
注意当选择了0个数时不更新答案。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const long long inf=1e18+7;
long long a,b,p[3005],ans;
bool cmp(const long long &a,const long long &b)
{
return a>b;
}
long long gcd(long long a,long long b)
{
return b==0?a:gcd(b,a%b);
}
void dfs(int x,int y,long long z)
{
if(x>p[0])
{
if(y&1)
ans+=((y&1)?1:-1)*(b/z-(a-1)/z);
else if(y)
ans-=b/z-(a-1)/z;
return;
}
dfs(x+1,y,z);
long long tmp=z/gcd(p[x],z);
if((double)p[x]*tmp<=b)
dfs(x+1,y+1,p[x]*tmp);
}
int main()
{
for(long long i=1;i<=10;i++)
for(long long j=0;j<(1<<i);j++)
{
long long now=0ll;
for(long long k=1,b=j;k<=i;k++,b>>=1)
{
if(b&1)
now=now*10+8;//9
else
now=now*10+6;//2
}
p[++p[0]]=now;
}
sort(p+1,p+1+p[0]);
for(long long i=1;i<=p[0];i++)
if(p[i]!=inf)
for(long long j=i+1;j<=p[0];j++)
if(p[j]%p[i]==0ll)
p[j]=inf;
sort(p+1,p+1+p[0]);
while(p[p[0]]==inf)
p[0]--;
sort(p+1,p+1+p[0],cmp);
scanf("%lld%lld",&a,&b);
dfs(1,0,1);
printf("%lld\n",ans);
return 0;
}