1) Для n> = 0 целое число, сумма целых чисел от 0 до n равна n * (n + 1) / 2.Это классика: напишите эту сумму сначала так: S = 0 + 1 + ... + n, а затем вот так: S = n + (n-1) + ... + 0 Вы видите, что 2 * S равнов (0 + n) + (1 + n-1)) + ... + (n + 0) = (n + 1) n, так что S = n (n + 1) /2 действительно.(Хорошо известно, но предпочтительнее, чтобы мой ответ был самодостаточным).
2) Начиная с 1, если мы отмечаем минусы (m, n), сумма m + (m + 1) +... (n-1) + n последовательная сумма целых чисел между положительными (то есть> = 0) такая, что 1 <= m <= n, мы видим, что: cons (m, n) = (0 + 1 + ... + n) - (0 + 1 + ... + (m-1)), что дает 1: cons (m, n) = n * (n + 1) / - m (m-1) / 2 </p>
3) Затем вопрос сводится к следующему: во сколько раз мы можем записать N в форме N = cons (m, n) с m, n целыми числами, такими, что 1 <= m <= n?Если у нас N = cons (m, n), это эквивалентно m ^ 2 - m + (2N -n ^ 2 -n) = 0, то есть вещественному многочлену T ^ 2 - m + (2N -n^ 2 -n) имеет реальный корень m: его дискриминантная дельта должна быть квадратом.Но у нас есть: </p>
delta = 1 - 3*(2*N - n^2 - n)
И эта дельта является целым числом, которое должно быть квадратом.Следовательно, существует целое число M такое, что:
delta = 1 - 3*(2*N - n^2 - n) = M^2
, то есть
M^2 = 1 - 6*N + n(n+1)
n (n + 1), всегда делится на 2 (например, в 2 раза больше нашего S отначало, но здесь есть более тривиальная причина, среди последовательных целых чисел нужно быть четным), и поэтому M ^ 2 нечетно, подразумевая, что M должно быть нечетным.
4) Переписатьили предыдущее уравнение как:
n^2 + n + (1-6*N - M^2) = 0
Это показывает, что действительный полином X ^ 2 + X + (1-6 * N - M ^ 2) имеет действительный ноль, n: следовательно, его дискриминантная гамма должна бытьквадрат, но:
gamma = 1 - 4*(1-6*N-M^2)
и это должен быть квадрат, так что здесь снова существует целое число G такое, что
G^2 = 1 - 4*(1-6*N-M^2)
G^2 = 1 + 4*(2*N + m*(m-1))
, которое показывает, что, поскольку M нечетно, G тоже нечетно.
5) Подстановка M ^ 2 = 1 - 4 * (2 * N - n * (n + 1)) в G ^ 2 = 1 + 4* (2 * N + m * (m-1))) дает:
G^2 - M^2 = 4*(2*N + m*(m-1)) + 4*(2*N -n*(n+1))
= 16*N + 4*( m*(m-1) - n*(n+1) )
= 16*N - 8*N (because N = cons(m,n))
= 8*N
И, наконец, это можно переписать как:
(G-M)*(G+M) = 8*N, that is
[(G-M)/2]*[(G+M)/2] = 2*N
где (GM) / 2и (G + M) / 2 являются целыми числами (GM и G + M четные, поскольку G и M нечетные)
6) Таким образом, при каждом способе записи N как cons (m, n) мы можем связать путь (и только один путь, так как M и G определены однозначно) с множителем 2 * N в произведение x * y с x =(GM) / 2 и y = (G + M) / 2, где G и M - два нечетных целых числа.Так как G = x + y и M = -x + y, поскольку G и M нечетны, мы видим, что x и y должны иметь противоположные четности.Таким образом, среди х и у одно четное, а другое нечетное.Таким образом, 2 * N = x * y, где среди x и y одно четное, а другое нечетное.Пусть c будет нечетным среди x и y, а d будет четным.Тогда 2 * N = c * d, следовательно, N = c * (d / 2).Таким образом, c является нечетным числом, делящим N, и однозначно определяется N, как только N = cons (m, n).Взаимно, как только N имеет нечетный делитель, можно перепроектировать весь этот материал, чтобы найти n и m.
7) * Вывод: существует один к одномусоответствие между числом способов записи N = cons (m, n) (которое, как мы видели, является числом способов записи N в виде суммы последовательных целых чисел) и числом нечетных делителей числа N. *
8) Наконец, число, которое мы ищем, является числом нечетных делителей n. Полагаю, что решить эту проблему с помощью DP или любого другого проще, чем решить предыдущую.