Нет ли более эффективного решения вопроса CodeForces 919-B/Perfect Number?

Ваша интуиция верна: это решение — наивный перебор, который работает для небольших случаев, но растет в O(n²) и так быстро замедляется по мере роста k. Для этого есть решение O(1) (постоянное время):
Этот вопрос уже поднимался ранее на сайте math stackexchange, и на него был получен прекрасный ответ с описанием оптимального решения здесь.

Редактировать:
Я пропустил часть о том, что сумма цифр равна ровно 10, а не делится на 10...
В этом случае я не уверен, есть ли оптимизация, поскольку вы действительно полностью зависите от всех цифр вашего ввода. Решение Саши по математическому вопросу не относится к вашему случаю.
Максимум, что я могу придумать для оптимизации вашего случая, - это сделать перерыв раньше, как только ваша сумма превысит 10, а также разбить большие числа на более мелкие части и вычислить их суммы параллельно, поскольку все они независимы друг от друга.

Ну, вы всегда можете сделать это с помощью динамического программирования.

Пусть на каждом шаге V[s] — вектор чисел с суммой цифр, равной s. (0<=с<=10).

На следующем шаге вы формируете V[s] из каждой цифры d, поочередно отмеченной перед всеми элементами в Vold[s-d]. Если вы отпустите d от 0 до min(9,s), то они будут сохранены по порядку. Остановитесь, когда V[10] наберет достаточно элементов.

Однако пришлось хранить числа в виде строк, поскольку некоторые из промежуточных чисел должны иметь 0 впереди.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

string kth( int k )
{
   const string digits = "0123456789";
   vector<vector<string>> V( 11 );          // V[s] is the vector of strings whose digits sum to s
   for ( int d = 0; d < 10; d++ ) V[d].emplace_back( string( 1, digits[d] ) );

   while( true )
   {
      auto Vold = V;                                       // previous values with one less digit
      V = vector<vector<string>>( 11 );                    // accumulate values with another digit at the front
      for ( int s = 10; s >= 0; s-- )                      // loop over sum of digits
      {
         for ( int d = 0; d <= min(s,9); d++ )             // loop over the new first digit
         {
            for ( const string &number : Vold[s-d] )       // new sum s from   digit=d + old sum=(s-d)
            {
               V[s].emplace_back( digits[d] + number );
               if ( s == 10 && d != 0 )                    // a "perfect" (ahem!) number found
               {
                  k--;
                  if ( k == 0 ) return V[s].back();
               }
            }
         }
      }
   }
}


int main()
{
   int k;
// cout << "Enter k: ";
   cin >> k;
   cout << kth( k );
}

Выход для k = 10000:

10800100

Но со струнами можно, по крайней мере, подняться несколько выше. Выход для k=10000000 (десять миллионов), очевидно,

1010110000111110010

Давайте представим, что вы хотите сгенерировать «идеальное» число (в данном контексте это означает число, сумма отдельных цифр которого равна 10) по заданному 10^k, игнорируя на данный момент тот факт, что вы хотите, чтобы они были сгенерированы на основе индекса.
Алгоритм, позволяющий это сделать:

1. Начните с 0, записанного с ведущими нулями, чтобы записанное число имело длину k: 0000000000 и k шаров в черном ящике с номерами от 0 до k-1.
2. Выберите случайный шар и назовите его значение i. Увеличьте i-ю цифру (условно от младшей к старшей) на 1,
   Вы получаете, например, 0000000100
3. Поместите мяч обратно в коробку.
4. Повторите шаги 2 и 3 9 раз (всего 10 раз).
   По построению вы получите идеальное число, например 0030200410.

Хотя приведенное выше не подходит для генерации «идеального» числа на основе его индекса (поскольку оно случайное), полезно понять, сколько существует совершенных чисел между 0 и 10^k.
Если вы не знаете, что это за число, я вам объяснил: оно называется комбинацией с повторениями, и вы можете прочитать об этом в этой статье в Википедии.

Удобно, что тот же принцип, который применяется к вытягиванию 9, 8, 7 и т. д. шаров, позволяет подсчитать, сколько совершенных чисел существует между любыми n₁ = 10^k i и n₂ = 10^k (i+1)-1. Например, существует 10 «идеальных» чисел между 214000 и 214999 (7 ​​вытянутых шаров, осталось 3 ничьи с 3 шарами в коробке), 4 между 214000 и 214099 (также 7 выпавших шаров, осталось 3 ничьи, но только с 2 мячи в коробке).

Обладая этими знаниями, мы можем инвертировать принцип, который заключается в подсчете количества совершенных чисел под любым заданным значением и сравнении его с входным индексом i:

1. Зная, сколько чисел меньше 10^k, мы можем сказать, сколько цифр имеет i-е совершенное число.
   На этом этапе мы должны быть осторожны и не учитывать комбинации, в которых один и тот же шар вытягивается 10 раз (если вы пропустили это выше, это реальная возможность для комбинаций с повторениями, и это явно не подойдет для вашей задачи).
   Если мы сделаем это правильно, мы гарантируем, что шар с номером k будет вытянут от 1 до 9 раз (и, как следствие, ни один из других шаров также не может быть вытянут 10 раз).
2. Зная, сколько чисел находится между 10^k и 2x10^k-1, мы можем определить, равна ли первая цифра, которую мы ищем, 1.
   Если нет, не беспокойтесь: повторяем расчет с диапазоном от 2x10^k до 3x10^k-1, затем от 3x10^k до 4x10^k-1 и т. д., пока не достигнем 10x10^k-1.
3. Определение первой цифры (n_k) похоже на вытягивание соответствующего количества одинаковых шариков из черного ящика.
   Следовательно, нам нужно только следить за тем, сколько шаров нам еще нужно вытянуть, и двигаться вниз, в убывающей степени 10.
4. По мере того, как мы продвигаемся вперед и шары с более высокими значениями удаляются из нашей коробки, в конечном итоге у нас остается только шар с номером 0. Это приводит к тому, что цифра единицы имеет уникальное значение (например, временный результат 17_ вынужден стать 172)

Случайность исчезла, и именно этого мы хотели, чтобы идеальные числа могли генерироваться по порядку.

Вот как это выглядит в коде; по сравнению с другим опубликованным ответом (на момент написания), он использует часть памяти и выполняется почти мгновенно (<1 мс). Я включил сравнение, если вы хотите попробовать (вам нужно будет скопировать функцию kth из другого ответа).

unsigned long long number_sum10(unsigned int index) 
{
    if (index == 0)
        throw std::runtime_error("Input cannot be 0.");

    auto combination_with_replacement = [](unsigned int number, unsigned int chosen = 10) -> unsigned long long
    {
        if (number == 0)
            return 1;
        unsigned long long result = chosen;
        for (decltype(number) i = 1; i < number; ++i) {
            result *= (chosen + i);
            result /= (i + 1);
        }
        return result;
    };

    unsigned int d = 1;
    unsigned long long count = 0, power = 1;
    for (; count < index; ++d) {
// Subtracting 1 from the combination count to avoid counting the invalid draws of 10x the same ball.
        count += combination_with_replacement(d) - 1;
        power *= 10;
    }
// Went 1 digit too far -> subtract to roll it back
    d -= 1;
    count -= combination_with_replacement(d) - 1;

    unsigned long long result = 0, digit = 1, ballsDrawn = 0;
    while (d > 0) {
        while (count < index) {
            auto toAdd = combination_with_replacement(d - 1, 11 - digit - ballsDrawn);
            if (count + toAdd >= index)
                break;
            digit += 1;
            count += toAdd;
        }
        ballsDrawn += digit;
        // Replace the next 2 lines with the commented line below to generate a std::string instead of unsigned long long with.
        result += power * digit;
        power /= 10;
        // result += std::to_string(digit);
        digit = 0;
        d -= 1;
    }

    result += 10 - ballsDrawn;
    return result;
}


#include <chrono>
#include <iostream>

int main(int, char**)
{
    using std::chrono::steady_clock;
    using std::chrono::duration_cast;
    using std::chrono::duration;
    using std::chrono::milliseconds;

    int k = 10000000;
    auto start = steady_clock::now();
    unsigned long long result1 = number_sum10(k);
    auto mid = steady_clock::now();
    std::string result2 = kth(k);
    auto end = steady_clock::now();
    std::cout << result1 << " vs " << result2 << " (" << (std::to_string(result1) == result2 ? "Same result" : "Unexpected difference") << ")\n";
    std::cerr << "Execution: " << duration_cast<milliseconds>(mid - start).count() << "ms vs " << duration_cast<milliseconds>(end - mid).count() << "ms\n";
}

Функция, которую я написал, возвращает unsigned long long, поэтому она переполнится после идеального числа 17 809 915^th (18 100 000 000 000 000 000), прямо под 2^64 = 18 446 744 073 709 551 616.

Чтобы выйти за рамки, необходимо преобразовать функцию так, чтобы:

• Он возвращает string (я поместил в свой код закомментированную «вспомогательную» строку, если вы хотите попробовать).
• Он возвращает больший целочисленный тип фиксированной ширины (например, boost::multiprecision::uint128_t).
• Он возвращает большой целочисленный тип из внешней библиотеки.
  Я протестировал модифицированную версию функции с типом bigint_t, определенным в этой библиотеке; все выглядит нормально.