[洛谷P2567] SCOI2010 幸运数字

问题描述

在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！但是这种“幸运号码”总是太少了，比如在[1,100]的区间内就只有6个（6，8，66，68，86，88），于是他又定义了一种“近似幸运号码”。lxhgww规定，凡是“幸运号码”的倍数都是“近似幸运号码”，当然，任何的“幸运号码”也都是“近似幸运号码”，比如12，16，666都是“近似幸运号码”。

现在lxhgww想知道在一段闭区间[a, b]内，“近似幸运号码”的个数。

输入格式

输入数据是一行，包括2个数字a和b

输出格式

输出数据是一行，包括1个数字，表示在闭区间[a, b]内“近似幸运号码”的个数

样例输入输出

样例输入

1 10

样例输出

数据范围

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

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

出处

四川省选2010

题目大意

定义集合(S)为包含所有([1,10^{10}])中仅由6和8构成的数字的倍数集合。求区([l,r])中属于(S)的元素个数。

解析

First of all

想到用类似于数位DP的方法，对每一位枚举选择哪个数，然后对每个构造出来的在区间([l,r])数验证是否是一个幸运数字的倍数。显然，这种做法的复杂度极其之高，我们可以换一种思路。

另一个思路

既然难以验证一个数是不是幸运数字的倍数，那么我们反过来，提前构造出所有幸运数字(具体可用搜索实现)，然后枚举他们的倍数，统计有多少个是在([l,r])中，得到答案。

如何统计呢？

引理

对于一个数(x),它在区间([l,r])的倍数个数为

[left lfloor frac{r}{x} ight floor - left lceil frac{l}{x} ight ceil+1 ]

所以，是不是对每一个幸运数字代入公式计算一下，累加答案就可以了呢？

容斥

答案是否定的。

一个很简单的道理，48是6和8的倍数，所以它会同时被6和8计算，也就是说，48被重复统计了一次。总结一下，任意几个幸运数字的(lcm)都会被重复统计。

拓展：(lcm)

(lcm(a,b))指的是(a)和(b)的最小公倍数。计算公式为(lcm(a,b)=a*b/gcd(a,b))

~~如果gcd也不知道就自行百度吧。~~

既然会重复统计(lcm)，我们就减掉一份两两最小公倍数带来的贡献。但是这样又会重复减掉任意三个数的最小公倍数的贡献，那么我们再加回来，又多加了任意四个数最小公倍数的贡献......。公式化之后就是

[ans=sum_{i}f(a[i])-sum_{i,j}f(lcm(a[i],a[j]))+sum_{i,j,k}f(lcm(a[i],a[j],a[k]))-...... ]

其中(f(x)=left lfloor frac{r}{x} ight floor - left lceil frac{l}{x} ight ceil+1)，(a[i])为第i个幸运数字。

搜索

有了容斥式，我们来考虑如何计算。用DFS可以很方便的解决。每次枚举一个数是否被选，最后如果选的数个数为奇数就加上(f(lcm))，否则减掉。

但这样还是不能通过。

剪枝

考虑类似于6和66的关系，66是6的倍数，那么66的倍数也都会被6计算到。所以，我们可以删去所有是其他幸运数字倍数的幸运数字。
如果当前(lcm)已经大于(r)，那么显然没有什么枚举下去的必要了。这时就可以剪枝。
可以把所有剩下的幸运数字从大到小排序后再DFS。这样在前几个阶段中就删去了很多(lcm)大于(r)的情况。

一个小问题

即便如此，这道题提交时还是会T几个点。原因是在计算DFS过程中计算(lcm)时(long long)溢出了。因此，我们需要使用(long double)类型计算避免此问题。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
const int lim=10000000000;
int i,j,l,r,num[1000002],cnt,n,ans;
bool vis[1000002];
void make(int x,int now)
{
	if(now>lim) return;
	if(now!=0) num[++cnt]=now;
	make(x+1,now*10+6);
	make(x+1,now*10+8);
}
int gcd(int a,int b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
void dfs(int x,int cnt,int lcm)
{
	if(x==n+1){
		if(lcm!=1) ans+=(cnt%2==0?-1:1)*(r/lcm-(l/lcm+(l%lcm==0?0:1))+1);
		return;
	}
	dfs(x+1,cnt,lcm);
	long double tmp=1.0*lcm/gcd(lcm,num[x])*num[x];
	if(tmp>r) return;
	dfs(x+1,cnt+1,tmp);
}
int my_comp(const int &x,const int &y)
{
	return x>y;
}
signed main()
{
	cin>>l>>r;
	make(0,0);
	sort(num+1,num+cnt+1);
	for(i=1;i<=cnt;i++){
		for(j=i+1;j<=cnt;j++){
			if(num[j]%num[i]==0) vis[j]=1;
		}
	}
	for(i=1;i<=cnt;i++){
		if(!vis[i]) num[++n]=num[i];
	}
	sort(num+1,num+n+1,my_comp);
	dfs(1,0,1);
	printf("%lld
",ans);
	return 0;
}