Прежде всего, обратите внимание, что ваше постановление проблемы немного подозрительно. Если вы рассматриваете числа до 1015, то наибольшая сумма цифр, которую вы можете получить, составляет от 999 и составляет 27. Следовательно, мы уже знаем, сколько чисел имеют сумму 27 < c <= 135;).
Далее ваш алгоритм выполняет довольно ненужные вычисления. Для каждого числа в диапазоне вы используете модуль для пересчета каждой отдельной цифры, когда в большинстве случаев меняется только одна цифра. Ваш код мог бы быть улучшен, если бы вы хранили цифры в массиве, увеличивали число «вручную» и складывали элементы массива. Хотя это не улучшит комплексность.
Попробуйте взглянуть на проблему с другой точки зрения. В основном вам нужно найти комбинации из четырех цифр, такие, что w+x+y+z = c и «объединение» этих цифр попадает в диапазон [a,b]. Например, когда c==4, тогда существует только несколько комбинаций:
1111, 211, 121, 112, 31, 22, 13
Если у вас есть эти числа, подсчитать, сколько из них попадает в данный диапазон, просто.
В шутку я решил посмотреть, можно ли реализовать стратегию перебора для вычисления во время компиляции. Мы можем вычислить сумму цифр следующим образом:
template <int x>
using number = std::integral_constant<int,x>;
template <int x>
struct sum_of_digits : number< sum_of_digits<x/10>::value + (x%10)> {};
template <>
struct sum_of_digits<0> : number<0> {};
Я использую помощника, чтобы проверить, равны ли два целых числа
template <int x,int y>
struct equals : std::false_type {};
template <int x>
struct equals<x,x> : std::true_type {};
Соединяя их вместе, мы можем проверить, имеет ли число заданную сумму цифр:
template <int x,int c>
struct is_sum_of_digits : equals<c,sum_of_digits<x>::value> {};
Теперь мы считаем числа с правильной суммой цифр в [0,a]:
template <int a,int c>
struct count : number<is_sum_of_digits<a,c>::value + count<a-1,c>::value> {};
template <int c>
struct count<0,c> : number<0> {};
Для примера я использую только трехзначные числа. Пределом является рекурсия шаблона из std::index_sequence, который я использую. Возможно, вам придется развернуть ваш -ftemplate-depth, чтобы он скомпилировался для большего количества цифр, и мне пришлось развернуть одно из измерений, чтобы не превысить мой предел компиляторов. С результатами времени компиляции я заполняю таблицу поиска, чтобы получить результаты во время выполнения:
const int max_b = 100; // max sum of digits is 18 for 99
template <std::size_t ... is>
int get_number_of_correct_sum_impl(int a,int b,int c,std::index_sequence<is...>){
static constexpr int table[] = { count<is,0>::value...,
count<is,1>::value... , count<is,2>::value... ,
count<is,3>::value... , count<is,4>::value... ,
count<is,5>::value... , count<is,6>::value...,
count<is,7>::value... , count<is,8>::value... ,
count<is,9>::value... , count<is,10>::value... ,
count<is,11>::value... , count<is,12>::value... ,
count<is,13>::value... , count<is,14>::value... ,
count<is,15>::value... , count<is,16>::value... ,
count<is,17>::value... , count<is,18>::value...
};
auto index = [max_b = max_b](int a,int c){ return c*max_b + a; };
return table[index(b,c)] - table[index(a,c)];
}
int get_number_of_correct_sum(int a,int b,int c){
return get_number_of_correct_sum_impl(a,b,c,std::make_index_sequence<max_b>{});
}
Тогда
int main() {
for (int i=1;i<33;++i){
std::cout << i << " " << get_number_of_correct_sum(0,i,5) << "\n";
}
}
Печать:
1 0
2 0
3 0
4 0
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 2
15 2
...etc...
Обратите внимание, что это все еще просто грубая сила, проверяющая все числа и подсчитывающая, сколько из них выполняет условие, но это делается во время компиляции. Все, что остается во время выполнения, - это просмотреть две записи в таблице поиска и определить их разницу, т.е. O(1).
Live Demo
PS: Кредиты за помощь по справочной таблице идут на https://stackoverflow.com/a/55543931/4117728 и https://stackoverflow.com/a/55543946/4117728