bzoj 1853 容斥原理

在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如12，16，666都是“近似幸运号码”。 现在lxhgww想知道在一段闭区间[a, b]内，“近似幸运号码”的个数。 Input 输入数据是一行，包括2个数字a和b Output 输出数据是一行，包括1个数字，表示在闭区间[a, b]内“近似幸运号码”的个数 Sample Input 【样例输入1】 1 10 【样例输入2】 1234 4321 Sample Output 【样例输出1】 2 【样例输出2】 809 Hint

【数据范围】 对于30%的数据，保证1 < =a < =b < =1000000 对于100%的数据，保证1 < =a < =b < =10000000000

题意：

给出一个区间，让你求这个区间内的近似幸运数和幸运数有多少个

题解：

先把所有幸运数找出来，剔除后面容斥会导致重复的数字

然后进行容斥

一共进行2的n次方的选择

所以需要剪枝，剪枝注意数据会会超，所以用double

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define LL long long int m,n; LL l,r,a[3000],b[3000],ans; bool vis[3000]; void init(LL x) { if(x>r) return; if(x) a[m++]=x; init(x*10+6); init(x*10+8); } LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);} void dfs(int now,int cnt,LL x) { if(now>=n){ if(!cnt) return ; if(cnt&1) ans+=r/x-(l-1)/x; else ans-=r/x-(l-1)/x; return; } dfs(now+1,cnt,x); LL tmp=x/gcd(a[now],x); if((double)a[now]*tmp<=r) dfs(now+1,cnt+1,tmp*a[now]); } int main() { // freopen("in.txt","r",stdin); while(scanf("%lld%lld",&l,&r)!=EOF) { m=n=0; init(0); sort(a,a+m); memset(vis,0,sizeof(vis)); for(int i=0;i<m;i++){ if(!vis[i]){ b[n++]=a[i]; for(int j=i+1;j<m;j++) if(a[j]%a[i]==0) vis[j]=1; } } for(int i=0;i<n;i++) a[i]=b[n-i-1]; ans=0; dfs(0,0,1); printf("%lld\n",ans); } return 0; }