06/04/2025 18:35:21

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2818. Хитрость Пенелопы

Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Кроме того, против нас и другую придумала хитрость:
Ткань начала она ткать, станок у себя поместивши,
Тонкую, очень большую и нам объявила при этом:
– Вот что, мои женихи молодые (ведь умер супруг мой),
Не торопите со свадьбой меня, подождите, покамест
Савана я не сотку…
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ Одиссея, песнь 2

Пока Одиссей странствует по дальним краям, его дворец и все имущество оберегает верная супруга Пенелопа. Чтобы отделаться от назойливых женихов, она заявила каждому из них следующее: ежедневно она будет ткать новое прямоугольное полотно с целочисленными сторонами и площадью от $L$ до $R$ включительно. Пока полотна не будут повторяться, Пенелопа продолжит ждать Одиссея, и женихам не на что рассчитывать. Помогите сыну Одиссея Телемаху оценить, сколько различных полотен сможет соткать Пенелопа для каждого из женихов – а значит, сколько дней у него осталось на поиски отца.

В первой строке ввода содержится одно целое число $N$ – количество женихов, которым Пенелопа дала обещание ( $1<=N<=10^5$ ). В каждой из следующих $N$ строк указано по два целых числа $L$ и $R$ ( $1<=L<=R<=10^7$ ) – минимальная и максимальная площадь полотна, которое обещала соткать Пенелопа.

Выведите $N$ целых чисел, по одному на строке. Каждое число – общее количество различных прямоугольников с целыми сторонами, имеющих площадь от $L$ до $R$ включительно. Прямоугольники, получающиеся друг из друга поворотом, считаются различными.

Пример ввода

Пример вывода

3
5
4

Пояснение к примеру:
Первое обещание, площадь от 1 до 2: прямоугольники $1 xx 1, 1 xx 2, 2 xx 1$ – всего 3.
Второе обещание, площадь от 3 до 4: прямоугольники $1 xx 3, 3 xx 1, 1 xx 4, 4 xx 1, 2 xx 2$ – всего 5.
Третье обещание, площадь 6: прямоугольники $1 xx 6, 6 xx 1, 2 xx 3, 3 xx 2$ – всего 4.

29/09/2024	Очный тур личного первенства по спортивному программированию (10)
30/09/2024	Дорешивание личных соревнований (2+ курсы) (проводит BOGAT) (K)