Loading [MathJax]/jax/output/CommonHTML/jax.js

Задача N. Два измерения

Автор:Центральная предметно-методическая комиссия   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Ученые планируют провести важный эксперимент с использованием исследовательского модуля на планете X-2019. В процессе эксперимента будет проведено два измерения: основное и контрольное. Каждое измерение занимает ровно один час и должно начинаться спустя целое число часов после начала работы исследовательского модуля.

Данные эксперимента планируется немедленно передать на орбитальную станцию. Канал связи с орбитальной станцией будет установлен с l-го по r-й час от начала работы исследовательского модуля, включительно. Кроме того, согласно плану эксперимента между измерениями планета должна совершить целое число оборотов вокруг своей оси. Планета X-2019 осуществляет оборот вокруг своей оси за a часов.

Таким образом, если измерения осуществляются на i-м и j-м часу, то должно выполняться неравенство lijr, а величина (ji) должна быть кратна~a. Теперь учёным необходимо понять, сколько существует различных способов провести измерения.

Требуется написать программу, которая по заданным границам времени измерений l и r и периоду обращения планеты вокруг своей оси a определяет количество возможных способов провести измерения: количество пар целых чисел i и j, таких что lijr, и величина (ji) кратна a.

Формат входных данных

Входные данные содержат три целых числа, по одному на строке: l, r и a.

Формат выходных данных

Выведите одно целое число: количество способов провести измерения.

Ограничения

1lr109, 1a109

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
1301lr100, 1a100полная
2301lr105, 1a1051полная
3401lr109, 1a1091, 2полная

Пояснения к примерам

В первом примере можно провести измерения в следующие пары часов: (1,3), (1,5), (2,4), (3,5).

Во втором примере продолжительности работы канала связи недостаточно, чтобы провести два измерения.

Примеры тестов

Стандартный вход Стандартный выход
1
1
5
2
4
2
4
9
6
0

0.043s 0.008s 15