Здравствуйте, Assasin291, Вы писали:

A>Здравствуйте. Есть задача: на вход поступают числа A, B, S, T, k, где
A>1 <= A, B <= 10^19;
A>1 <= S, T <= 162;
A>2 <= k <= 100.
A>Нужно найти количество всех чисел, которые находятся на интервале [A, B], имеют сумму цифр, принадлежащих отрезку [S, T] и в то же время делятся на k без остатка.

A>Прямой перебор здесь не подходит. Как можно поступить в таком случае?

Это довольно стандартная задача на динамическое программирование.

Во-первых, научимся находить количество чисел <= X, обладающих всеми свойствами относительно суммы цифр и делимости. Пусть таких чисел будет F(X). Тогда ответ на исходную задачу будет F(B) — F(A-1). Теперь, как искать F(X)?

Пусть X у нас задано, и в нем n цифр. Будем искать все n-значные числа с заданной суммой и делящиеся на k. Представим что мы записываем число слева направо (со старших разрядов). Допустим, мы записали уже i цифр. Тогда нас интересуют следующие свойства записанного числа: остаток от деления на k (обозначим q), сумма цифр (обозначим s) и то, гарантирует ли записанный префикс, что любое число с этим префиксом меньше X (обозначим l, это булевский флаг). Посчитаем количество чисел которые можно получить из префикса длины i с остатком q, суммой s и флагом l, так чтобы они удовлетворяли всем условиям задачи и были меньше X. Обозначим это количество как F(i, q, s, l).

Тогда какие у нас варианты? Если l == true, то есть префикс заведомо меньше X, мы можем приписать любую цифру справа. Получается:

F(i, q, s, true) = sum(d in [0..9], F(i+1, (q*10 + d) mod k, s + d, true)

Если l == false:

F(i, q, s, false) = sum(d in [0..X[i]], F(i+1, (q*10 + d) mod k, s + d, d < X[i])

Где X[i] — это i-я цифра числа X (нумерация с 0, 0 — самый старший разряд).

Тогда F(X) = F(0, 0, 0, false)

начальные условия:

F(n, q, s, l) = 1 if q == 0 and S <= s <= T else 0, где n — длина числа X.

Получилась рекуррентная формула, которую осталось только запрограммировать (с мемоизацией).