1717: Два вимірювання

View as PDF

Submit solution

Points: 25
Time limit: 2.0s
Memory limit: 500M

Author:
Problem type

Вчені планують провести важливий експеримент з використанням дослідного модуля на планеті X-2019. В процесі експерименту буде проведено два вимірювання: основне та контрольне. Кожне вимірювання займає рівно одну годину і має починатися через ціле число годин після початку роботи дослідницького модуля. Дані експерименту планується негайно передати на орбітальну станцію. Канал зв'язку з орбітальною станцією буде встановлений з \(l\)-ї по \(r\)-у годину від початку роботи дослідного модуля, включно. Крім того, згідно з планом експерименту між вимірюваннями планета повинна зробити ціле число обертів навколо своєї осі. Планета X-2019 здійснює оберт навколо своєї осі за \(a\) годин. Таким чином, якщо вимірювання здійснюються на \(i\)-й та \(j\)-й годині, то повинна виконуватися нерівність \(l \le i < j \le r\), а величина (\(j - i\)) повинна бути кратна \(a\). Тепер вченим необхідно зрозуміти, скільки існує різних способів провести вимірювання.

Потрібно написати програму, яка за заданими межами часу вимірювань \(l\) і \(r\) та періодом обертання планети навколо своєї осі \(a\) визначає кількість можливих способів провести вимірювання: кількість пар цілих чисел \(i\) та \(j\), таких що \(l \le i < j \le r\), і величина (\(j - i\)) кратна \(a\).

Формат вхідних даних

Вхідні дані містять три цілих числа, по одному на рядку: \(l\), \(r\) і \(a\) (\(1 \le l < r \le 10^9\), \(1 \le a \le 10^9\)).

Формат вихідних даних

Виведіть одне ціле число: кількість способів провести вимірювання.

Примітка

До прикладу 1:

У першому прикладі можна провести вимірювання в наступні пари годин: (1, 3), (1, 5), (2, 4), (3, 5).

У другому прикладі тривалості роботи каналу зв'язку недостатньо, щоб провести два вимірювання.

Оцінювання

Підзадача 1: 30 балів, \(1 \le l < r \le 100, 1 \le a \le 100\);

Підзадача 2: 30 балів, \(1 \le l < r \le 10^5, 1 \le a \le 10^5\);

Підзадача 3: 40 балів, \(1 \le l < r \le 10^9, 1 \le a \le 10^9\),

Приклад вхідних даних

1
5
2

Приклад вихідних даних

4

Приклад вхідних даних

4
9
6

Приклад вихідних даних

0

Comments

There are no comments at the moment.