开始: 2025-08-22 11:00:00

暑期训练赛S01

结束: 2025-09-06 11:00:00
当前  2025-09-26 06:41:17  类型: IOI  状态: 已经结束 

P3. 互质序列(rlprime)
描述

给出两个数 A, BB \geq A),问有多少个序列满足以下条件:

1. 序列是递增的。

2. 所有数字属于区间 [A, B](包括 A 和 B,B - A \leq 100)。

3. 序列中的所有数字两两互质。


输入

一行输入两个数 A、B。其中 1 \leq A \leq B \leq 1e18B - A \leq 100

输出

输出对应的答案。

样例

输入

2 4

输出

5
提示

- 对于 25% 的数据:1 \leq A \leq B \leq 10^7B - A \leq 30

- 对于 40% 的数据:1 \leq A \leq B \leq 10^{12}B - A \leq 50

- 对于 100% 的数据:1 \leq A \leq B \leq 10^{18}B - A \leq 100

样例解释:

满足条件的序列为:(2)、(3)、(4)、(2,3)、(3,4)。

提交

题目参数
时间限制 1 秒
内存限制 256 MB
提交