「BZOJ1853」[SCOI2010] 幸运数字

2014年4月27日15,6730

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

题解

此题数据范围是真正的10^10,于是我们需要一些方法来防止爆long long

就是这段

if(((double)a[x]*tmp)<=r) dfs(x+1,y+1,a[x]*tmp);

因为a[x]*tmp可能超过long long,于是我们先用double存它的近似值,如果它小于r,则一定在long long范围内,就可以直接乘了

其余同2393

 

avatar
  Subscribe  
提醒