bzoj#P2713. [Violet 2]愚蠢的副官

[Violet 2]愚蠢的副官

题目描述

宇宙纪元 45 年, D 将军与大魔王在银河两岸对垒。
为了指挥方便, D 将军将自己的防线从 OO 开始标号,一直到某个难以计数的量(鉴于 D 军威武雄壮,军势浩大,我们可以认为最大标号大于 101810^{18} ,而小于 101910^{19} )。
他的得力军师 L 参谋在每个整点处部署了一支分队,以保防线无虞,避免大魔王的偷袭。

D 将军身经百战,勇武无双,乃是全宇宙首屈一指的名将;麾下 L 参谋智勇双全,运筹帷握,更是全宇宙绝无第二的奇才。
不过俗话说得好,双拳难敌四手,独木难支,尽管手下不乏猛将谋臣,他们还是想培养能独当一面的帅才。
于是 D 将军和 L 参谋决定让 Z 副官重新调度防线,来组织一次小规模的进攻。

尽管 D 、 L 二人在战场上所向披靡,可由于国家政策上的漏洞,手下的人才质与量都让人心优。
靠着小心眼和小算盘爬到副官一职上的 Z 副官就是一例。
他尽管口若悬河,但实乃败絮其中:正所谓笔下虽有千言,胸中实无一策。
他平日里夸夸其谈,但只是纸上谈兵:若要真让他带兵,他反倒没了主意。
打小喜欢玩数字游戏的他,于是下达了这样一条指令:原来处于位置 nn 的部队,转调到 nn 与其各位数字之积的位置上。
比如原来驻守在 312312 坐标的 X 队长,将移驻到 312×3×1×2=1872312 \times 3 \times 1 \times 2 = 1872 坐标处。
毫无疑问, 00 坐标处会集结大量的部队, Z 副官将组织部队从此处发动进攻。

在 Z 副官指挥调度之时, D 、 L 两人正在其他的防线视察。
所以当他们回到前线时,他们被 Z 副官的调度计划惊呆了。
整个防线因此而残破不堪,部队散落不均,根本无法抵挡大魔王的冲击。
幸好 D 、 L 二人手中还有后备军,他们决定赶紧将后备军安排到前线。
不过由于时间紧张,他们只能填补一段防线的空缺。
他们找到了身为士官的你,要你告诉他们某段防线上现在有几支部队。
由于他们并不打算参与 Z 副官的愚蠢进攻,所以他们不关心 00 点处的部队。

输入格式

输入只有一行,包含两个整数 a,ba , b ,代表 D 将军和 L 参谋询问的区间 [a,b][a,b]

输出格式

输出一个数字,表示 [a,b][a,b] 中现有的部队数。

137 801
39

数据规模与约定

  • 对于 20%20\% 的数据,保证 a,b1000a,b \le 1000
  • 对于 40%40\% 的数据,保证 a,b106a,b \le 10^6
  • 对于 100%100\% 的数据,保证 1a,b10181 \le a,b \le 10^{18}

题目来源

Croatian2008 Umnozak