@asyl_narul

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

Сколькими способами можно представить заданное натуральное число N в виде суммы после-
довательных нечетных натуральных чисел? Одно число «суммой» не считается.

Пример: 16 можно представить двумя способами 1 + 3 + 5 + 7 = 16 и 7 + 9 = 16.
  • Вопрос задан
  • 2632 просмотра
Решения вопроса 2
wataru
@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, то прибавляйте единицу к ответу.
Ответ написан
Комментировать
longclaps
@longclaps
N выражается через сумму арифметической прогрессии, N = (a + n - 1) * n, где a - первый член прогрессии, n - количество членов.
Раскладываешь своё число на все возможные пары множителей и смотришь: пусть один из них n, будет ли тогда a нечетным натуральным? Это проще простого.
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы