Прошу подсказать алгоритм для поиска корней уравнения высшей степени. Конкретней: есть многочлен вида k[0] * x^n + k[1] * x ^ (n - 1) + ... + k[n - 1] k[i] принадлежит Z и |k[i]| <= 10^9.Известно, что все корни целые.
Ответ
Все целые корни многочлена с целыми коэффициентами являются делителями его свободного члена.
Поэтому есть такой путь:
1. Провести факторизацию свободного члена.
2. Найти все делители свободного члена как произведения его простых множителей (взятых в степенях не выше, чем в каноническом разложении), со знаками плюс и минус.
3. Отобрать все корни среди делителей.
На самом деле главная проблема - в нахождении одного корня x=a, поскольку в соответствии с теоремой Безу многочлен разделится на x-a, и следующий корень можно будет подставлять в частное. При этом повторная факторизация также получается путём несложного пересчёта.
Комментариев нет:
Отправить комментарий