You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

对于正整数 $n$，定义 $A_n$ 为 $1, 2, \dots, n$ 的最小公倍数。

$A_1=1,A_2=2,A_3=6,A_4=12,A_5=60,A_6=60,...$

给定正整数 $L, R$，请问数列 $(A_L, A_{L+1}, \dots, A_R)$ 中包含多少种不同的整数？

输入格式

输入以如下格式从标准输入读入。

$L$ $R$

输出格式

输出数列 $(A_L, A_{L+1}, \dots, A_R)$ 中不同整数的个数。

4 12

6

枚举 $A_4$ 到 $A_{12}$ 如下：

• $A_4 = 12$
• $A_5 = 60$
• $A_6 = 60$
• $A_7 = 420$
• $A_8 = 840$
• $A_9 = 2520$
• $A_{10} = 2520$
• $A_{11} = 27720$
• $A_{12} = 27720$

因此，$(A_4, A_5, \dots, A_{12})$ 中包含 $6$ 种不同的整数。

123456789 123456789

1

限制条件

30% $1 \le L \le R \le 5000$

70% $1 \le L \le R \le 10^6$

100% $1 \leq L \leq R \leq 10^{14}$ ; $R - L \leq 10^6$ ; $L, R$ 为整数

样例解释 1