/ 
実行時間制限: 4 sec / メモリ制限: 1024 MiB
配点 : 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}) には 6 種類の整数が含まれています。
入力例 2
123456789 123456789
出力例 2
1
入力例 3
99999990000000 100000000000000
出力例 3
310458
Score : 500 points
Problem Statement
For a positive integer n, define A_n as the least common multiple of 1, 2, \dots, n.
You are given positive integers L and R. How many distinct integers are contained in the sequence (A_L, A_{L+1}, \dots, A_R)?
Constraints
- 1 \leq L \leq R \leq 10^{14}
- R - L \leq 10^7
- L and R are integers.
Input
The input is given from Standard Input in the following format:
L R
Output
Output the number of distinct integers contained in the sequence (A_L, A_{L+1}, \dots, A_R).
Sample Input 1
4 12
Sample Output 1
6
Listing A_4 through 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
Thus, (A_4, A_5, \dots, A_{12}) contains six distinct integers.
Sample Input 2
123456789 123456789
Sample Output 2
1
Sample Input 3
99999990000000 100000000000000
Sample Output 3
310458