Целые корни многочлена

[hello19]

ИСН в сообщении #988757 писал(а):

Предложение есть, и я его повторял уже больше раз, чем обычно принято для задач с ProjectEuler:

ИСН в сообщении #988719 писал(а):

Но может быть, можно как-то лихо сразу, одним махом сказать, сколько из них имеют корнем $-1$, например?

что касается корня $-1$, то, имхо, можно вырисовывается критерий: сумма четных коэффициентов = сумме нечетных. Сколько таковых "пар" понятия пока не имею..

Ну а раз так, то можно как-то воспользоваться вот этим: http://www.genfunc.ru/theory/lucky/
Что думаете?

[ИСН]

atlakatl в сообщении #988758 писал(а):

А как оценить число полиномов $ax^2+bx+c=0$, имеющих корнем $-1$, области $(N; N; N)$? - Тут всё гораздо сложнее.

Вы всё правильно говорите, но не то. Надо не оценку, а точно. И полином не квадратный. Да и область-то не до N, а до 10. Разница

hello19 в сообщении #988760 писал(а):

вырисовывается критерий: сумма четных коэффициентов = сумме нечетных.

Вы где-то выше упоминали другое свойство, эквивалентное этому.

[hello19]

С распределениями ничего не выходит... видимо, стоит больше времени уделять аналитике...

[hello19]

[quote="ИСН в сообщении #988719"
Но может быть, можно как-то лихо сразу, одним махом сказать, сколько из них имеют корнем $-1$, например?[/quote]

Ну, например, можно взять остаток от деления максимального значения n (назовем его - N) на 11. Столько будет n, для которых соответствующий полином будет иметь корень -1.
Но среди таких n есть и те, полиномы которых имеют корень 0 - 110, например. Думаю, с этим как-то можно справиться.
Вопрос возникает, когда дело доходит до других делителей.

[Lia]

venco в сообщении #988723 писал(а):

Я думаю не стоит здесь обсуждать задачу 269 с ProjectEuler.

Соглашусь. Тем более, что подсказки уже прозвучали.

Закрыто.

[Lia]

Открыто по просьбе ТС.

[hello19]

venco в сообщении #988723 писал(а):

Я думаю не стоит здесь обсуждать задачу 269 с ProjectEuler.

Погуглив, нашел ответ на эту задачу: https://code.google.com/p/projecteuler- ... rSolutions
Так что вред "олимпиаде" этой я своей темой, как мне кажется, не наношу..
Меня же интересует не ответ, а само решение.

И так, на данный момент дошел до лишь до того, чтобы посчитать сколько есть полиномов, имеющих корень $-1$.
Думал, посчитать количество полиномов, имеющих корни $-1$ и $0$ по формуле включений-исключений, т.е. так: (кол-во полиномов, имеющих корень -1) $+$ (кол-во полиномов, имеющих корень -1) $-$ (кол-во полиномов, имеющих корень -1 и 0)

итого, зная, что для N=100000 (таковых - 14696) рассчитываю:
$\frac{100000}{10} + \frac{100000}{11} - \frac{100000}{110} = 10000 + 9090 - 909 = 18181 > 14696$ (а ведь там еще и другие корни есть)
Где я ошибаюсь?

[venco]

hello19 в сообщении #989040 писал(а):

Где я ошибаюсь?

Возьмите, например, 627.

[hello19]

venco в сообщении #989064 писал(а):

hello19 в сообщении #989040 писал(а):

Где я ошибаюсь?

Возьмите, например, 627.

Да, попадаются, например, кратные 11, но не имеющие корня -1, такие как 209
Нужно как-то научится обходить это..

[hello19]

Вот как выглядят n, для корней с $-4$ по $-9$ и только для них... т.е. $-1$ среди корней нет (запускал для $ n \leqslant 10000000$, само собой тут не все):

$ -9: 19 - 1919 - 190019 - 191919 - 1901919 - 1919019 -8: 18 - 1818 - 1998 - 18198 - 19818 - 180018 - 180198 - 181818 - 181998 -7: 17 - 1717 - 1887 - 17187 - 18717 - 170017 - 170187 - 171717 - 171887 -6: 16 - 1616 - 1776 - 16176 - 17616 - 160016 - 160176 - 161616 - 161776 -5: 15 - 1515 - 1665 - 15165 - 16515 - 150015 - 150165 - 151515 - 151665 -4: 14 - 28 - 294 - 1414 - 1428 - 1554 - 1568 - 2814 - 2828 - 2954 - 2968 $

Пока что-то не осилил найти зависимость того, является ли только одно число (любое от -4 до -9) корнем полинома (не учитываю корни, для которых -1 корень)

знак "-" идет как разделитель.