Bez użycia jakichkolwiek wbudowanych funkcji faktoringowych / wielomianowych, rozkład wielomian całkowicie na nieredukowalne ponad liczbami całkowitymi lub polem skończonym.
Wejście
Twój program / funkcja otrzyma pewną liczbę pierwszą (lub zero) n
jako dane wejściowe. Pole / pierścień jest skończonym polem tego rzędu (tj. Z/nZ
) Lub tylko Z
jeśli n
jest 0
. Twój program może się nie powieść, jeśli n
nie jest 0
to podstawowa liczba. Wielomian będzie w F[x]
.
Twój program / funkcja otrzyma również wielomian jako dane wejściowe.
Dane wejściowe są trochę elastyczne, pamiętaj o określeniu, w jaki sposób zamierzasz otrzymywać dane wejściowe. Na przykład wielomian może być wprowadzony jako lista współczynników lub w formie, jakiej większość ludzi oczekuje (np .:) 50x^3 + x^2
, lub w innej rozsądnej formie. Lub format wprowadzania pola / pierścienia może być również inny.
Wynik
Twój program / funkcja wyprowadzi wielomian faktoryzowany całkowicie. Możesz pozostawić rozwinięte wiele korzeni (tzn. (x + 1)(x + 1)
Zamiast (x + 1)^2
). Możesz usunąć spacje między operatorami binarnymi. Możesz zamienić zestawienie na *
. Możesz wstawiać białe znaki w dziwnych miejscach. Możesz zmienić kolejność czynników w dowolnej kolejności. x
Termin może po prostu być (x)
. x
można zapisać jako x^1
; jednak stały termin może nie mieć x^0
. Obce +
znaki są dopuszczalne. Możesz nie mieć terminu z 0
przodu, należy je pominąć. Termin wiodący każdego czynnika musi być dodatni, znaki ujemne muszą znajdować się na zewnątrz.
Przypadki testowe, twój program powinien być w stanie wygenerować dane wyjściowe dla każdego z nich w rozsądnym czasie (powiedzmy <= 2 godziny):
Wejście: 2, x^3 + x^2 + x + 1
Wynik: (x + 1)^3
Wejście: 0, x^3 + x^2 + x + 1
Wynik: (x + 1)(x^2 + 1)
Wejście: 0, 6x^4 – 11x^3 + 8x^2 – 33x – 30
Wynik: (3x + 2)(2x - 5)(x^2 + 3)
Wejście: 5, x^4 + 4x^3 + 4x^2 + x
Wynik: x(x + 4)(x + 4)(x + 1)
Wejście: 0, x^5 + 5x^3 + x^2 + 4x + 1
Wynik: (x^3 + 4x + 1)(x^2 + 1)
Specjalne podziękowania dla Petera Taylora za krytykę moich przypadków testowych
p
ma elementy{0, 1, ... , p-1}
i jest w trakcie dodawania / mnożeniap
. Zasadniczo zmniejsz dowolny współczynnik przez modp
i jesteś dobry. Zauważ też, że jeśli ma pierwiastek, tzn. Współczynnik liniowy, jeden z{0, ... , p-1}
nich wytworzy0
(modp
), gdy jest podłączony do wielomianu.Z
jest uwzględnienieZ/pZ
odpowiedniego,p
a następnie henselowego wzrostu . Jednak podejście do gry w golfa jest prawdopodobnie (i z pewnością jest to trasa, na którą patrzę), aby użyć prostego ograniczenia na wysokości czynników i brutalnej siły.Odpowiedzi:
GolfScript (222 bajty)
Demo online
Uwagi
n
następuje tablica współczynników GolfScript od najbardziej do najmniej znaczących. Np.0, x^5 + 5x^3 + x^2 + 4x + 1
Należy sformatować jako0 [1 0 5 1 4 1]
.Z
.Z
Poradzę sobie , używając zrelaksowanej formy związanej z wysokością Mignotte. Świetny artykuł na temat granic wysokości w faktorowaniu to Bounds on Factors w Z [x] , John Abbott, 2009 (link jest do prefiksu arxiv; jego CV mówi, że został zaakceptowany przez Journal of Symbolic Computation ). Najbardziej zrelaksowana forma podana jest pod względem normy L-2, ale aby zaoszczędzić bajty, relaksuję się dalej i zamiast tego używam normy L-1. Potem chodzi o brutalne zmuszanie przez podział próbny.Z
tylko pierścień, dlatego konieczne jest dzielenie prób według niemonicznych czynników kandydujących. Udaje mi się nie wdrożyć liczb wymiernych, przeprowadzając test wiodącego podziału czynników i gromadząc flagę „błąd”e
.Z
jest ogólnie wolniejszy i nie można go przetestować za pomocą demonstracji online. Jednak najwolniejszy z oficjalnych przypadków testowych zajmuje 10 minut, co dobrze mieści się w „rozsądnym” terminie.źródło