Контрольная работа: Використання модульної арифметики. Обчислення з многочленами. Методи множення. Складність обчисл

У загальному вигляді можна записати

ця формула показує, яким чином з коефіцієнтів можна отримати коефіцієнти :

Послідовно виходять коефіцієнти багаточленів

Відповідно до останньої таблиці ми маємо

Отже, відповіддю до нашої вихідної задачі буде де виходить у результаті дій додавання і зрушення. Крім того, якщо коефіцієнти багаточлена – ненегативні, то такими будуть і числа , а тоді всі проміжні результати, одержувані в процесі проведення обчислення, є ненегативними.