Руст писал(а):
Пусть

где

все корни уравнения:

.
Сумма берётся по всем

от

до

, то есть суммируются ровно

чисел. Между тем у уравнения возможны кратные корни, в связи с чем количество корней может быть меньше, чем

. Я понимаю это так, что корни суммируются с учётом их кратности, то есть каждый корень суммируется столько раз, какова его кратность. Если я неправильно понял условие, то пусть автор задачи меня поправит.
Руст писал(а):
Вычислить

Вероятно, звёздочка обозначает здесь умножение. То есть надо вычислить

. Если нет, то опять же пусть автор меня поправит.
Итак, пусть

и

--- примитивный корень

-ой степени из

. Пусть также

. Пусть теперь
Видно, что

является корнем

тогда и только тогда, когда для некоторых
![$i \in [1,2009]$ $i \in [1,2009]$](https://dxdy-01.korotkov.co.uk/f/0/3/4/0343d9192e449479f885ebb8f327035882.png)
и
![$j \in [1,n]$ $j \in [1,n]$](https://dxdy-03.korotkov.co.uk/f/2/d/f/2df982b5c0eb594b64d1073c38d5d88482.png)
справедливо

, причём кратность каждого такого корня равна кратности корня

при

и кратности

, умноженной на

, при

. Это значит, что
Заметим, что

. Отметим также, что

и, как следствие этого,
Пусть теперь

--- такой многочлен, что

, то есть
По теореме Виета число

равно коэффициенту многочлена

при

, то есть коэффициенту многочлена

при

. Вычислим этот коэффициент.
Имеем

. Пусть

--- множество всех таких троек

, что

,

и

--- подмножества множества

, образующие разбиение этого множества (то есть

,

и

попарно не пересекаются и в объединении дают всё

) и

. Тогда искомый коэффициент равен
Здесь для произвольного конечного множества чисел

запись

означает сумму всех элементов

,

.
Пусть

, то есть

. Тогда

. Так как

, то

. Однако

, так что

. Отсюда

. Так как число

кратно

, то получаем две возможности:

и

. При

имеем

и

, а при

выполняется

и

.
Отметим, что в каждом из случаев для любого

, такого что

равно

или

, существуют единственные

и

, для которых тройка

. Значит, искомую сумму можно расписать в виде
где

и

определяются из условия

.
Если

, то

и

. Если же

, то

,

и

. Кроме того, легко видеть, что

. Таким образом, искомая сумма равна
или, после некоторых сокращений,
Найдём, чему равно
Из простых комбинаторных рассмотрений ясно, что эта сумма равна коэффициенту при

многочлена
Так как

и

--- примитивный корень степени

из

, то

, где

--- примитивный корень степени

из

. Значит, этот многочлен равен
Соответствующий коэффициент, как легко видеть из бинома Ньютона, равен

. Таким образом,
Найдём, чему равно
Из тех же соображений, что и при нахождении предыдущей суммы, заключаем, что эта сумма равна минус коэффициенту при

многочлена
Обозначив за

число

и заметив, что

есть примитивный корень

-ой степени из

, переписываем этот многочлен как
Из бинома Ньютона находим, что коэффициент при

у этого многочлена равен

.
Таким образом,
и
Ответ, однако, отличается от того, который получил
juna. Поскольку он не приводит никаких выкладок, желающие могут проверить моё решение и либо убедиться в его правильности, либо найти в нём ошибку.