Можно попробовать сделать микрооптимизации: функция F реализуется одним циклом (делите, пока делится на 10, потом берите последнюю цифру). S тоже можно считать циклом, а не рекурсией.
Но скорее всего, этого не хватит. Это решение за O(q*log(q)). Ограничения на числа в условии не видно, но если там что-то порядка 2000000000, то ваша программа будет считать несколько секунд.
Надо хорошенько подумать и применить математическую хитрость. Надо как-то считать числа в интервале p...q пачками, а не каждое отдельно.
Что такое функция F? Это последняя ненулевая цифра в числе. Давайте вместо суммы значений F счиатать, сколько чисел из интервала дадут вот такое вот значение? Ну просто по последней цифре сложно сказать, сколько там чисел, а вот если еще зафиксировать количество пропущенных в конце нулей, то уже становится понятно, как подсчитать это. Вот допустим, вы считаете последнюю цифру d и там должно быть 3 нуля. Тогда вы ищети числа вида "xxxd000". Или их можно представить в виде d*1000+x*10000 для произвольного неотрицательного x. И вот вам надо подсчитать сколько таких чисел в интервале [p,q]. Ну решите 2 уравнения: d*1000+x*10000 >= p и d*1000+x*10000 <= q
Таким образом вы за несколько арифметических действий и одну проверку можете подсчитать, сколько чисел вида "xxxd000" будут в интервале. Осталось циклом перебрать d от 1 до 9 и количество нулей от 0 до длины q. И вот у вас решение за O(log(q)).
Edit:
Вот код быстрого решения:
int S(int p, int q) {
int sum = 0;
for (int d = 1; d < 10; ++d) {
for (int tens = 1; tens <= q; tens *= 10) {
int left = p - d*tens;
if (left < 0) left = 0;
else left = (left + 10*tens-1)/(10*tens);
int right = q - d*tens;
if (right < 0) right = -1;
else right /= 10*tens;
sum += d*(right - left + 1);
}
}
return sum;
}
