- Решение
Решение
Заметим, что xd+8n = xd для любого натурального числа n. Вектору x = (x1, … , x8) взаимно-однозначно соответствует многочлен x(t) = x1 + x2t + ⋯ + x7t6 + x8t7 . Тогда циклический сдвиг вектора x на d позиций вправо равносилен умножению многочлена x(t) на td и приведению степеней мономов по модулю 8. Вектору x = v + v1 + v4 соответствует многочлен x(t) = 1 + t + t4 . Таким образом, нахождение d1, … , dn таких, что xd1 + … + xdn равносильно нахождению многочлена v(t) = td1 + ⋯ + tdn со свойством x(t)v(t) = 1 (с учётом приведения степеней мономов по модулю 8). Найти многочлен v(t) можно методом неопределённых коэффициентов, но быстрее из следующего алгоритма: x(t) 2 = 1 + t + t8 = t 2 , x(t)4 = t4 , x(t)8 = t8 = 1. Следовательно, v(t) = x(t)7 = x(t) 3x(t)4 = (1 + t + t4 )t2 t4 = t2+ t6 + t7.
- Ответ