容斥原理
计算近似幸运数字的个数，就是总个数减去不是近似幸运数字的数的个数
首先用一个dfs筛出所有10位以内的幸运数字，然后再把倍数筛掉
最后运用容斥原理，Dfs筛一遍就好了
这个Dfs是一个补集的容斥
具体请看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
long long a,b,us[2505],siz,ne[2505],nen;
void dfs(int w,long long x){
if(w>10)return;
us[++siz]=x;
dfs(w+1,x*10ll+6);
dfs(w+1,x*10ll+8);
}
bool cmp(long long as,long long bs){
return as>bs;
}
long long gcd(long long s1,long long s2){
return !s2?s1:gcd(s2,s1%s2);
}
long long Dfs(int i,long long nu){
if(i>nen)return b/nu-a/nu;
long long ans=Dfs(i+1,nu),g=gcd(ne[i],nu);
if(nu/g<=b/ne[i])ans-=Dfs(i+1,nu/g*ne[i]);
return ans;
}
int main(){
freopen("1853.in","r",stdin);
freopen("1853.out","w",stdout);
scanf("%lld %lld",&a,&b);
dfs(1,6);
dfs(1,8);
sort(us+1,us+siz+1,cmp);
for(int i=1;i<=siz;i++){
int flag=0;
for(int j=siz;j>i;j--){
if(us[i]%us[j]==0){
flag=1;
break;
}
}
if(flag==0)ne[++nen]=us[i];
}
a--;
printf("%lld\n",b-a-Dfs(1,1));
return 0;
}
评论 (0)
