시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 5 | 1 | 1 | 50.000% |
Целое число $x$ называется свободным от квадратов, если нет такого целого числа $y > 1$, что $x$ делится на $y^2$, то есть $x = y^2z$ для некоторого целого $z$.
Даны числа $l$ и $r$. Требуется найти число пар целых чисел $(a, b)$, таких что $l \le a < b \le r$, и числа $a$, $b$, а также их произведение $ab$ свободны от квадратов.
На вход подается две строки, первая содержит целое число $l$, а вторая --- целое число $r$ ($1 \le l < r \le 10^9$, $r - l \le 1000$).
Выведите одно целое число --- искомое число пар.
3 6
2
В примере подходят пары $a = 3, b = 5$, $a = 5, b = 6$. Число $4$ не может входить в пару, так как $4 = 2^2\cdot 1$, а пара $a = 3, b = 6$ не подходит, так как $ab = 3\cdot 6 = 18 = 3^2\cdot 2$.