「BZOJ2393」Cirno的完美算数教室

2014年4月26日3,2894

Description

~Cirno发现了一种baka数,这种数呢~只含有2和⑨两种数字~~
现在Cirno想知道~一个区间中~~有多少个数能被baka数整除~
但是Cirno这么天才的妖精才不屑去数啦
只能依靠聪明的你咯。

Input

一行正整数L R
( 1 < L < R < 10^10)

Output

一个正整数,代表所求的答案

Sample Input

1 100

Sample Output

58

HINT

此题数据范围应该是10^9

10^9中只含2和9的数,且不被其它这样的数整除的baka数只有30个左右

于是我们可以利用容斥原理,加上奇数个集合的并,减去偶数个集合的并

 

说点什么

提醒
avatar
婷小葵葵葵

素数是什么鬼啊…应该是那些不能被其他只含2和9整除的数?

黄学长的小号
黄学长的小号

这题和只含2和9的质数有什么关系?