← 返回题目列表

AtCoder · abc412_e

H. LCM 序列

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

对于正整数 n,定义 A_n 作为最小公倍数 1, 2, \dots, n.
给你正整数 L 和 R。序列中包含多少个不同的整数 (A_L, A_{L+1}, \dots, A_R)?

约束

  • 1 \leq L \leq R \leq 10^{14}
  • R - L \leq 10^7
  • L 和 R 是整数。

输入

输入由标准输入按以下格式给出:

L R

输出

输出序列中包含的不同整数的数量 (A_L, A_{L+1}, \dots, A_R).


示例输入 1

4 12

示例输出 1

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}) 包含六个不同的整数。


示例输入 2

123456789 123456789

示例输出 2

1

示例输入 3

99999990000000 100000000000000

示例输出 3

310458