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

Можно, конечно, перебирать все числа, делящиеся на k и смотреть сумму их цифр, но это будет очень долго. Поэтому хочу спросить, можно ли как-то связать сумму цифр с делимостью на k, или хотя бы считать сумму цифр не применяя всё время функцию, которая находит эту сумму вычисляя остаток от деления числа на степени 10?

В общем случае нет.

Применяя методы работы, используемые в примитивных реализациях длинной арифметики (хранить число как поразрядный массив цифр), можно сильно ускорить процесс.

Да, знаю, но на тест даётся всего 1 секунда. Даже если использовать длинную арифметику такой скорости работы не добиться.

А может можно за одну-две итерации найти сумму цифр следующего числа, принадлежащего [S, T], зная сумму цифр предыдущего с суммой цифр из этого же отрезка? То есть, например, если взять промежуток от 17 до 26:

17:
089, 098; //2 числа
179, 188, 197; //3 числа
269, 278, 287, 296; //4числа
и т. д.
18:
99; //новый
189, 198; //2 числа с суммой цифр 17, к которым я добавил 1 в разряд сотен
279, 288, 237; //3 числа -//-
339, 378, 387, 396; 4 числа -//-

Есть сложности при переходе на старший разряд(есть условия, когда добавление единицы даст число с меньшей суммой + если интервал меньше n*3 и больше (n+k) * 3, то тоже не понятно, как действовать при подобном быстром поиске суммы цифр числа).

a=1
b=10^19
s=1
t=162
k=2
Даже при всей очевидности ответа 1 секунды не хватит не то что на вывод - даже на безалгоритмическую генерацию 5*10^18 чётных чисел.
Можете смело говорить, что с учётом ограничения по времени в общем случае задача не решается.

Извиняюсь, надо найти не конкретно числа, а их количество.