Подсчитать, сколько счастливых чисел лежат в интервале [a, b].

Назовём число счастливым, если оно делится на k и сумма его цифр лежит в интервале [p, q]. Подсчитайте, сколько счастливых чисел лежат в интервале [a, b].

Формат входных данных
Первая строка содержит десятичную запись числа k (1 ≤ k ≤ 100).
Вторая строка — числа a и b (1 ≤ a, b < 10^19).
Третья — десятичную запись чисел p и q (1 ≤ p, q ≤ 162).

Короче, я расписал алгоритм к этой задаче:
1. Пишем функцию, которая будет находить сумму цифр чисел.
2. Далее заполняем вектор числами от a до b.
3. Каждое число проверяем на кратность числу K, если не кратно - удаляем из вектора (либо же можем все числа, которые кратны переместить в другой вектор)
4. После каждый из элементов вектора проверяем на принадлежность суммы цифр заданному интервалу, если не принадлежит - удаляем. (аналогично можем поместить пушбеком все числа, которые соответствуют условию в ещё один вектор).
5. Далее считаем кол-во элементов в итоговом векторе и выводим результат.

Есть проблема, в данной задаче 1<=a b <10^19, т.е. огромные числа.
Помогите подправить алгоритм, дабы решить задачу.

0

С динамическим программированием знакомы?

0

LegionK, косвенно

0