[luogu2576 SCOI2010] 幸运数字 (容斥原理)

传送门

Description

在中国，很多人都把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 10

Sample Output

2

HINT

对于30%的数据，保证1<=a<=b<=1000000

对于100%的数据，保证1<=a<=b<=10000000000

Solution

预处理幸运号码（极少），去掉其中互为倍数的

dfs枚举其中的数，求lcm用边界除一下就得到倍数个数

考虑容斥，算完即可

Code

//By Menteur_Hxy

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define F(i,a,b) for(register int i=(a);i<=(b);i++)

using namespace std;

typedef long long LL;

const int N=3010;

bool vis[N];

int n,m;

LL l,r,ans;

LL a[N],b[N];

void pre(LL x) {

	if(x>r) return ;

	if(x) a[++n]=x;

	pre(x*10+6);pre(x*10+8);

}

LL gcd(LL a,LL b) {return !b?a:gcd(b,a%b);}

void dfs(int x,int y,LL z) {

	if(x>m) {

		if(y&1) ans+=r/z-(l-1)/z;

		else if(y) ans-=r/z-(l-1)/z;

		return ;

	}

	dfs(x+1,y,z);

	LL tmp=z/gcd(a[x],z);

	if((double)a[x]<=(double)r/tmp) //防爆类型

		dfs(x+1,y+1,a[x]*tmp);

}

int main() {

	scanf("%lld%lld",&l,&r);

	pre(0); sort(a+1,a+1+n);

	F(i,1,n) if(!vis[i]) {

		b[++m]=a[i];

		F(j,i+1,n) if(a[j]%a[i]==0) vis[j]=1;

	}

	F(i,1,m) a[i]=b[m-i+1];

	dfs(1,0,1);

	printf("%lld",ans);

	return 0;

}