Представить число в виде суммы последовательных слагаемых

Есть переменная a, а может быть любым числом. Допустим a = rand()%10+1; И надо найти все возможные варианты сложения. Представить целое число a в виде суммы как минимум двух последовательных натуральных чисел.
Например:
10 = 1 + 2 + 3 + 4 24 = 7 + 8 + 9
Помогите найти и придумать алгоритм поиска. Спасибо.

Ответ

Смотрите, всё не так сложно. Это простое диофантово уравнение.
Вспомним формулу суммы арифметической прогрессии (у нас разность d = 1, n — неизвестное количество слагаемых, a_1 — неизвестное первое слагаемое):
S = n * (2 * a_1 + (n - 1)) / 2
Отсюда 2S делится на n
Дальше легко найти кандидатуры на n перебором как делители 2S. Например, для S = 10 это будут 2, 4, 5, 10, 20, n = 1 отбрасываем, у нас должно быть больше одного слагаемого. Для каждого из них находим 2S / n = 2 * a_1 + (n - 1), а потом и a_1 (у нас получится соответственно 4.5, 1, 0, -3.5, -9). Отбрасываем дробные результаты, и получаем ответы:
1 + 2 + 3 + 4 0 + 1 + 2 + 3 + 4 -9 + -8 + -7 + -6 + -5 + -4 + -3 + -2 + -1 + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
Если нужно только натуральные числа, оставляем только варианты с a_1 > 0, это будет
1 + 2 + 3 + 4

Асимптотическая сложность: простейшее разложение на множители перебором до корня O(sqrt(n)), проверка каждого кандидата O(1).