[SCOI2010]幸运数字 [容斥原理 dfs]

题意：“幸运号码”是十进制表示中只包含数字6和8的那些号码，求\([l,r]:r \le 10^10\)之间“幸运号码”的倍数个数

发现幸运号码貌似很少唉，去掉幸运号码的倍数只有943个

直接统计有重复，考虑容斥

怎么算？

多个数的倍数就是他们的\(lcm\)的倍数，直接搜索，当前\(lcm>r\)就剪掉，从大到小来加速

然后求\(lcm\)会爆long long，先整除判一下



这是不等式的放缩吗？

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int N=3e3+5;

typedef unsigned long long ll;

inline ll read(){

	char c=getchar();ll x=0,f=1;

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

	return x*f;

}

ll l, r;

int n, vis[N]; ll a[N];

void dfs(ll now) {

	if(now>r) return;

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

	dfs(now*10+6);

	dfs(now*10+8);

}

inline ll gcd(ll a, ll b) {return b==0 ? a : gcd(b, a%b);}

ll ans;

void dfs(int c, ll now, int p) {

	if(now>r) return;

	if(c) ans += (c&1) ? r/now - (l-1)/now : -(r/now - (l-1)/now);

	for(int i=p; i<=n; i++) {

		ll t = now/gcd(now, a[i]);

		if(t <= r/a[i]) dfs(c+1, t*a[i], i+1);

	}

}

int main() {

	freopen("in","r",stdin);

	l=read(); r=read();

	dfs(0);

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

	for(int i=1; i<=n; i++) if(!vis[i])

		for(int j=i+1; j<=n; j++) if(!vis[j] && a[j]%a[i] == 0) vis[j]=1;

	for(int i=1; i<=n; i++) if(!vis[i]) a[++a[0]]=a[i];

	n=a[0];

	printf("n %d\n",n);

	reverse(a+1, a+1+n);

	dfs(0, 1, 1);

	printf("%lld",ans);

}