3
9
2016
0

[BZOJ1853] [Scoi2010]幸运数字

容斥原理

计算近似幸运数字的个数,就是总个数减去不是近似幸运数字的数的个数

首先用一个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;
}
Category: BZOJ | Tags: OI bzoj | Read Count: 582

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com