Python: Сколькими способами можно представить заданное натуральное число N в виде суммы после- довательных нечетных натуральных чисел?

Question

[Леша Да]

Сколькими способами можно представить заданное натуральное число N в виде суммы после-
довательных нечетных натуральных чисел? Одно число «суммой» не считается.
Пример: 16 можно представить двумя способами 1 + 3 + 5 + 7 = 16 и 7 + 9 = 16.

Answer 1

[Wataru]

Сумма последовательных нечетных чисел - разность двух квадратов:

1 + 3 + 5 + 7 = 16 - 0
7 + 9 = 25 - 9

Таким образом - вопрос в том, сколько различных пар квадратов дают разность в заданное N.

N = a^2 - b^2 = (a-b)(a+b)

Или же сколько чисел a и b, т.ч. N раскладывается на множители (a+b) и (a-b).

Достаточно найти все делители N (не больше корня) т.ч. делитель и оставшаяся часть имеют четную разность (эта разность же равна 2b). Т.е. (n/d - d) %2 = 0.

Перебирайте все числа d до корня N, и если N%d == 0 and (N/d -d) %2 == 0, то прибавляйте единицу к ответу.

Answer 2

[longclaps]

N выражается через сумму арифметической прогрессии, N = (a + n - 1) * n, где a - первый член прогрессии, n - количество членов.
Раскладываешь своё число на все возможные пары множителей и смотришь: пусть один из них n, будет ли тогда a нечетным натуральным? Это проще простого.