Счастливые номера маршруток


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 3.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Пассажиры бишкекских маршруток считают номер билета счастливым, если он делится на сумму своих цифр. Например, 132 счастливый (1 + 3 + 2 = 6, 132 = 6 · 22), а 133 — нет.

Рисунок

Для каждого из T вопросов l r найдите количество счастливых чисел среди l, l + 1, …, r.

Входные данные

В первой строке — число T (1 ≤ T ≤ 10). В каждой из следующих T строк — два целых числа l r (1 ≤ l ≤ r ≤ 10¹⁸).

Выходные данные

Для каждого вопроса выведите количество счастливых чисел на отрезке.

Пример 1

Вход:

3
1 20
100 200
1 100000

Выход:

13
27
11872

Пояснение

Однозначные числа счастливы все, из чисел 10…20 счастливы 10, 12, 18, 20. Всего на отрезке от 1 до 20 их 13.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 15 % тестов r ≤ 10⁶, ещё в 5 % тестов r ≤ 10⁹.

Подсказка

Переберите сумму цифр S (от 1 до 162) и для каждой посчитайте числа с суммой цифр S, делящиеся на S, — динамикой по цифрам.


Комментарии

Еще нет ни одного комментария.