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) njako dane wejściowe. Pole / pierścień jest skończonym polem tego rzędu (tj. Z/nZ) Lub tylko Zjeśli njest 0. Twój program może się nie powieść, jeśli nnie jest 0to 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. xTermin może po prostu być (x). xmoż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 0przodu, 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}

GolfScript (222 bajty)

~.@:q@.0\{abs+}/2@,2/)?*or:^{\1$^base{^q- 2/-}%.0=1=1$0=q>+{{:D[1$.,2$,-)0:e;{.0=0D=%e|:e;(D(@\/:x@@[{x*~)}%\]zip{{+}*q!!{q%}*}%}*e+])0-{;0}{@;@\D.}if}do}*;\).^3$,)2/?<}do;][[1]]-{'('\.,:x;{.`'+'\+'x^'x(:x+x!!*+\!!*}%')'}/

Demo online

Uwagi

1. Po formacie wejściowym nnastępuje tablica współczynników GolfScript od najbardziej do najmniej znaczących. Np. 0, x^5 + 5x^3 + x^2 + 4x + 1Należy sformatować jako 0 [1 0 5 1 4 1].
2. Na skończonym polu istnieje tylko skończenie wiele wielomianów o wystarczająco małym stopniu, aby były istotne. Tak jednak nie jest Z. ZPoradzę 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.
3. Na skończonym polu każdy wielomian jest stałą razy wielomian moniczny, więc robię próbny podział tylko według wielomianów monicznych i zapisuję odwrotność w polu. Jest to jednak Ztylko 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.
4. Zarówno punkty 2, jak i 3 sugerują, że przypadek faktoringu Zjest 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.