【BZOJ1853/2393】[Scoi2010]幸运数字/Cirno的完美算数教室 DFS+容斥

时间：2022-07-18 23:24:42

【BZOJ1853】[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】
1 10
【样例输入2】
1234 4321

Sample Output

【样例输出1】
2
【样例输出2】
809

HINT

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

题解：显然由6和8组成的数一共也没有多少个，我们可以先将这些数全部枚举出来。然后自然想到容斥，总数=能被一个数整除的-能被2个数整除的+能被3个数整除的。。。。

然后试了一下，极限数据跑得奇慢无比。于是看题解，发现需要先把那些数中能相互整除的去掉，并且枚举顺序要改成从大到小，这技巧也是神了~

#include <cstring>

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long ll;

ll v[3000],w[3000];

ll L,R,ans;

int n,m;

void init(ll now)

{

	if(now>R)	return ;

	if(now)	w[++m]=now;

	init(now*10+6),init(now*10+8);

}

ll gcd(ll a,ll b)

{

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

}

void dfs(int x,ll now,int f)

{

	if(x>n)	return ;

	for(int i=x;i<=n;i++)

	{

		ll g=gcd(now,v[i]);

		if(R/(v[i]/g)/now-L/(v[i]/g)/now)

		{

			ll tmp=v[i]*now/g;

			ans+=f*(R/tmp-L/tmp),dfs(i+1,tmp,-f);

		}

	}

}

int main()

{

	scanf("%lld%lld",&L,&R),L--;

	init(0);

	sort(w+1,w+m+1);

	int i,j;

	for(i=1;i<=m;i++)	if(w[i]!=-1)	for(j=i+1;j<=m;j++)

		if(w[j]%w[i]==0)	w[j]=-1;

	for(i=m;i>=1;i--)	if(w[i]!=-1)	v[++n]=w[i];

	dfs(1,1,1);

	printf("%lld",ans);

	return 0;

}//1 10000000000

相关文章