Фонари на каждой k-й улице

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

Мэрия решила поставить фонари на улицах, номер которых делится на k. Инспектору дали один район — от улицы a до улицы b (включительно) — и попросили быстро понять, сколько улиц в этом районе получат фонари.

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

Формат ввода

В одной строке записаны три целых числа a, b, k.

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

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

Ограничения

• 1 ≤ a ≤ b ≤ 10^9
• 1 ≤ k ≤ 10^9

Пример

Ввод:

3 17 5

Вывод:

3

Ключевое наблюдение: вместо перебора улиц на отрезке удобно уметь быстро отвечать «сколько чисел от 1 до x делятся на k». Это число равно x // k, потому что каждое k-е число даёт одно кратное: k, 2k, 3k, …, (x//k)·k.

Дальше отрезок [a, b] получается разностью двух префиксов: все кратные до b минус все кратные до a-1.

Почему приём работает: множество чисел на [a, b] — это числа на [1, b] без чисел на [1, a-1]. Для количества это означает вычитание.

План решения:

• Прочитать a, b, k.
• Посчитать cntB = b // k — сколько кратных k на [1, b].
• Посчитать cntA = (a - 1) // k — сколько кратных k на [1, a-1].
• Ответ: cntB - cntA.

Мини-сниппет формулы: ans = b//k - (a-1)//k.

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

Частая ошибка: забыть про a-1 и вычесть a//k — тогда вы потеряете кратное, если само a делится на k, или наоборот получите лишнее в других случаях.