Лягушка и прыжки
Сумма арифметической прогрессии натурального ряда чисел, проверка числа на его "целостность"
Лягушка живет на координатной оси oX в точке 1. Она решила переместиться в точку n, в которой живет ее друг. Для перемещения лягушка может выбрать целое положительное число x и совершать прыжки вправо, причем длина первого прыжка будет равна x, длина второго прыжка будет равна x + 1, длина третьего прыжка будет равна x + 2 и так далее. Другими словами, длина i-го прыжка лягушки будет равна x + i - 1. Лягушка хочет выбрать число x таким образом, чтобы попасть с помощью прыжков из точки 1 строго в точку n. Количество прыжков может быть произвольным. Помогите лягушке и определите количество различных чисел x, с помощью которых она может попасть из точки 1 в точку n, а также сами значения x.
Входные данные
В первой строке следует целое число n (2 <= n <= 10^12) — точка, в которую нужно попасть лягушке.
Выходные данные
В первую строку выведите целое число p — количество различных x, выбрав которые, лягушка может попасть из точки 1 строго в точку n.
Во вторую строку выведите p целых чисел — значения x, выбрав которые, лягушка может попасть из точки 1 строго в точку n.
Каждое из подходящих значений x должно быть выведено ровно один раз. Все подходящие значения x должны быть выведены в строго возраста
ПОЯСНЕНИЕ
Зададимся вопросом: на какую длину сместится лягушка после i-го прыжка, если длина первого прыжка
L1 = x
L1 = x
L2 = L1 + 1 = x + 1
L3 = L2 + (x + 2) = (x + 1) + (x + 2) = 2x + 3
L4 = L3 + (x + 3) = (2x + 3) + (x + 3) = 3x + 6
L5 = L4 + (x + 4) = (3x + 6) + (x + 4) = 4x + 10
Можем заметит, что числа 1, 3, 6, 10 являются суммами арифметических прогрессий S(i) натурального ряда чисел:
S(1) = 1
S(2) = 1 + 2 = 3
S(3) = 1 + 2 + 3 = 6
S(4) = 1 + 2 + 3 + 4 = 10
Таким образом, после i-го прыжка лягушка сместится на расстояние:
Вспоминая формулу арифметической прогрессии натурального ряда S(n) = n * (n + 1) / 2, получим
Li = (i - 1) * x + (i - 1) * ((i - 1) + 1) / 2
или
Li = (i - 1) * x + i * (i - 1) / 2
или
Li = (i - 1) * (x + i / 2)
Тогда после i-го шага лягушка должна оказаться в точке с координатой
n = Li + 1 (нарисуй рисунок и убедись!)
или
n = (i - 1) * (x + i / 2) + 1,
выразим отсюда x
x = (n - 1) / (i - 1) - i / 2,
приводя к общему знаменателю, получим
x = (2 * (n - 1) - i * (i - 1)) / (2 * (i - 1)) (*)
Задачу можно сформулировать следующим образом:
необходимо найти все i, для которых выражение (*) одновременно удовлетворяет следующим условиям:
- x <= n (лягушка не перепрыгнула через друга)
- x > 0 (целое положительное число, оказывается можно подобрать такое количество прыжков i, что x окажется меньше нуля)
- x целое число (из условия ясно, что координаты целые числа)
Примечание: формула (*) применима для i > 1 (при i = 1, знаменатель обращается в ноль)
АЛГОРИТМ
- Для n = 2 вывести ответ (наша формула не работает для данного случая)
- Перебрать по порядку все возможные i начиная с двух, пока x не станет больше n или меньше нуля
- Перебрать в обратном порядке все возможные i, начиная со значения, получившегося в п.2, до двух.
3.1 При этом необходимо выводить только целые значения координаты x. Не забыть добавить 1
2.1 При этом необходимо подсчитать, для скольких i, значение координаты x целое число.
