UOJ Logo Universal Online Judge

UOJ

#188. 【UR #13】Sanrd

统计

这里是跳蚤国中央广播电台,现在为您转播的是著名人类智慧大师 picks 博士与人工智能 betacome 之间的最后一轮赛事。

这一场交锋的规则由网友 st****ll 提供,这位网友也将获得由不想跳的跳蚤不是好跳蚤——最强跳蚤跳跳跳公司提供的金牌跳蚤一只。

就在刚才,第二轮比赛也已经结束了,picks 博士不负众望为人类扳回了一城。特别是在刚才劣势的时候,picks 博士突然地停止了对盘子的操作,让 betacome 乱了阵脚,并最后实现了反超,这一手操作也被网友戏称为“神之一手”。

“恩,这一手表明了 betacome 也是存在弱点而不是不可战胜的,picks 博士可能也在一直尝试着不同的比赛风格,试图找到 betacome 的漏洞。上一场的胜利说明了 betacome 在对于突发事件的应对方式可能存在着缺陷,在这一轮 picks 博士应该会针对这一点进行比赛,我认为他的胜率应该会非常大。”

那看来 A 先生抱着非常乐观的心态啊,现在最后一轮的比赛已经开始了,同样,接下来由 A 先生来给我们介绍一下这一轮比赛的规则。

“好,大家现在看屏幕,在这一轮游戏中,给出了一个如下所示的将 $n$ 分解质因子的算法。”

  1. 检查$n$是否是质数,假如$n$是质数或$n=1$则直接结束。
  2. 定义一个变量$p$,初始值为2。
  3. 检查$p$是否是$n$的因子,假如$p$是$n$的因子,不断将$n$除去$p$,直到$p$不再是$n$的质因子。
  4. 检查$n$是否是质数,假如$n$是质数或$n = 1$,就结束这个算法,否则将$p$的值加一,返回第三步。

“为了检验人类智慧和人工智能之间的计算能力的差距,主办方希望选手对区间 $[l,r]$ 中的所有数都用这个算法进行分解。为了检验计算的正确性,选手需要计算分解完每一个数后,$p$ 的和。特殊地,如果分解在第一步就结束了,那么就认为 $p=0$。

恩,谢谢 A 先生。大家可以看到这一道是数论方面的题目,刚才 A 先生也私下和我说了,这一道题目的难度要比前两轮的难度高很多,他认为在短时间内,比赛双方都无法得到准确的结果。因为我们节目组决定与观众们进行互动,正在收看节目的观众可以关注节目跳蚤信公众号参与解题,最快得到正确答案的观众将会获得由不想跳的跳蚤不是好跳蚤——最强跳蚤跳跳跳公司提供的精美礼品一份。

作为一名光荣的吃土少年,你立志要把这份礼品收入囊中以告别悲惨的吃土生活。然而,全世界的观众中也不乏人类智慧大师的存在,为了从他们中脱颖而出,你需要以最快的速度得到这一个问题的答案。

输入格式

第一行两个正整数 $l,r$,表示需要分解的数的范围。

输出格式

输出一行一个整数,表示每次分解结束时,变量 $p$ 的值之和。

C/C++ 输入输出 long long 时请用 %lld

样例一

input

16 20

output

7

explanation

需要分解的数是 $16 \sim 20$这五个数,其中 $17$ 和 $19$ 是质数,算法在第一步终止。

$16=2\times2\times2\times2$,算法运行到$p=2$时结束。

$18=2\times3\times3$,算法运行到$p=3$时结束。

$20=2\times2\times5$,算法运行到$p=2$时,$n$被除到了5,在第四步中被判定为质数后终止。

分解这五个数结束时的$p$的值为$\{2,0,3,0,2\}$。

所以答案是$2 + 0 + 3 + 0 + 2 = 7$。

样例二

input

35 3657

output

23333

样例三

input

10000002333 10002333333

output

5346939605

限制与约定

测试点编号 限制与约定
1$r \le 10 ^ 4$
2$r \le 10 ^ 7$
3$r \le 10 ^ 9$,$r - l \le 10 ^ 7$
4$r \le 10 ^ {10}$,$r - l \le 10 ^ 7$
5$r \le 3 \times 10 ^ {10}$,$r - l \le 10 ^ 7$
6$r \le 5 \times 10 ^ {10}$
7$r \le 7 \times 10 ^ {10}$
8$r \le 8 \times 10 ^ {10}$
9$r \le 9 \times 10 ^ {10}$
10$r \le 10 ^ {11}$

对于所有数据,$1\leq l\leq r$,$l + r \leq 10 ^ {11}$。

时间限制:$5\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载