Автор: | Центральная предметно-методическая комиссия | Ограничение времени: | 1 сек | |
Входной файл: | Стандартный вход | Ограничение памяти: | 512 Мб | |
Выходной файл: | Стандартный выход | |||
Максимальный балл: | 100 |
Ученые планируют провести важный эксперимент с использованием исследовательского модуля на планете X-2019. В процессе эксперимента будет проведено два измерения: основное и контрольное. Каждое измерение занимает ровно один час и должно начинаться спустя целое число часов после начала работы исследовательского модуля.
Данные эксперимента планируется немедленно передать на орбитальную станцию. Канал связи с орбитальной станцией будет установлен с l-го по r-й час от начала работы исследовательского модуля, включительно. Кроме того, согласно плану эксперимента между измерениями планета должна совершить целое число оборотов вокруг своей оси. Планета X-2019 осуществляет оборот вокруг своей оси за a часов.
Таким образом, если измерения осуществляются на i-м и j-м часу, то должно выполняться неравенство l≤i≤j≤r, а величина (j−i) должна быть кратна~a. Теперь учёным необходимо понять, сколько существует различных способов провести измерения.
Требуется написать программу, которая по заданным границам времени измерений l и r и периоду обращения планеты вокруг своей оси a определяет количество возможных способов провести измерения: количество пар целых чисел i и j, таких что l≤i≤j≤r, и величина (j−i) кратна a.
Входные данные содержат три целых числа, по одному на строке: l, r и a.
Выведите одно целое число: количество способов провести измерения.
1≤l≤r≤109, 1≤a≤109
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
---|---|---|---|---|
1 | 30 | 1≤l≤r≤100, 1≤a≤100 | полная | |
2 | 30 | 1≤l≤r≤105, 1≤a≤105 | 1 | полная |
3 | 40 | 1≤l≤r≤109, 1≤a≤109 | 1, 2 | полная |
В первом примере можно провести измерения в следующие пары часов: (1,3), (1,5), (2,4), (3,5).
Во втором примере продолжительности работы канала связи недостаточно, чтобы провести два измерения.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
2 |
|
|