Фонари на проспекте

В городе Нумерополис все дома на проспекте пронумерованы подряд: 1, 2, 3, ...

Мэр решил поставить одинаковые фонари у домов, чьи номера делятся на число k без остатка. Тебе поручили быстро посчитать, сколько таких домов попадёт на отрезок проспекта от дома l до дома r включительно.

Важно: значения могут не помещаться в 32-битный тип (как на олимпиадах), поэтому считай аккуратно.

Формат ввода

Одной строкой вводятся три целых числа k, l, r.

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

Выведите одно целое число — сколько чисел на отрезке [l, r] делятся на k.

Ограничения

• 1 ≤ k ≤ 10^9
• 1 ≤ l ≤ r ≤ 10^9

Пример

Ввод:

3 1 10

Вывод:

3

Ключевое наблюдение: числа, делящиеся на k, идут ровно через каждые k: k, 2k, 3k, … Поэтому вместо перебора от l до r (это слишком долго) можно посчитать, сколько кратных попадает в начало проспекта.

Приём: считаем «префиксную» функцию f(x) — сколько чисел на отрезке [1..x] делятся на k. Это просто x // k, потому что среди 1..x есть ровно столько полных групп по k.

Тогда ответ на [l..r] получается вычитанием: всё, что до r, минус всё, что строго до l, то есть до l-1.

План:

• Прочитай k, l, r.
• Посчитай a = r // k — количество кратных на [1..r].
• Посчитай b = (l - 1) // k — количество кратных на [1..l-1].
• Выведи a - b.

Мини-сниппет формулы:

• ans = r//k - (l-1)//k

Сложность: O(1) по времени и O(1) по памяти.

Частая ошибка: забыть про l-1 и посчитать r//k - l//k — это ломается, когда l само кратно k (например k=3, l=3, r=3: правильный ответ 1, а неверная формула даст 0).