Tanpa menggunakan fungsi anjak / polinomial bawaan, faktor polinom sepenuhnya menjadi irreducible atas bilangan bulat atau bidang terbatas.

Memasukkan

Program / fungsi Anda akan menerima beberapa bilangan prima (atau nol) nsebagai input. Bidang / cincin adalah bidang hingga dari urutan itu (yaitu Z/nZ), atau hanya Zjika nada 0. Program Anda mungkin gagal jika nbukan 0atau prima. Polinomial akan berada di F[x].

Program / fungsi Anda juga akan menerima input polinomial.

Ada beberapa fleksibilitas dalam input, pastikan untuk menentukan bagaimana Anda ingin menerima input. Misalnya, polinomial dapat menjadi input sebagai daftar koefisien, atau dalam bentuk yang kebanyakan orang harapkan (mis .:) 50x^3 + x^2, atau bentuk wajar lainnya. Atau format memasukkan bidang / dering juga bisa berbeda.

Keluaran

Program / fungsi Anda akan menampilkan faktor polinom sepenuhnya. Anda dapat membiarkan beberapa root diperluas (mis. (x + 1)(x + 1)Bukannya (x + 1)^2). Anda dapat menghapus spasi putih di antara operator biner. Anda dapat mengganti penjajaran dengan *. Anda dapat memasukkan spasi putih di tempat-tempat aneh. Anda dapat menyusun ulang faktor menjadi urutan apa pun yang Anda inginkan. The xjangka bisa saja (x). xdapat ditulis sebagai x^1; Namun istilah konstan mungkin tidak ada x^0. +Tanda-tanda asing diijinkan. Anda mungkin tidak memiliki istilah dengan 0di depan, mereka harus ditinggalkan. Istilah utama dari setiap faktor harus positif, tanda-tanda negatif harus di luar.

Uji kasus, program Anda harus dapat menghasilkan output untuk masing-masing dalam waktu yang wajar (katakanlah, <= 2 jam):

Memasukkan: 2, x^3 + x^2 + x + 1

Keluaran: (x + 1)^3

Memasukkan: 0, x^3 + x^2 + x + 1

Keluaran: (x + 1)(x^2 + 1)

Memasukkan: 0, 6x^4 – 11x^3 + 8x^2 – 33x – 30

Keluaran: (3x + 2)(2x - 5)(x^2 + 3)

Memasukkan: 5, x^4 + 4x^3 + 4x^2 + x

Keluaran: x(x + 4)(x + 4)(x + 1)

Memasukkan: 0, x^5 + 5x^3 + x^2 + 4x + 1

Keluaran: (x^3 + 4x + 1)(x^2 + 1)

_{Terima kasih khusus kepada Peter Taylor karena mengkritik kasus pengujian saya}

GolfScript (222 byte)

~.@:[email protected]\{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

Catatan

1. Format input ndiikuti oleh array koefisien GolfScript dari yang paling signifikan. Misalnya 0, x^5 + 5x^3 + x^2 + 4x + 1harus diformat sebagai 0 [1 0 5 1 4 1].
2. Di atas bidang yang terbatas, hanya ada banyak polinomial dengan derajat yang cukup kecil untuk menjadi relevan. Namun, ini belum berakhir Z. Saya mengatasinya Zdengan menggunakan bentuk santai dari batas tinggi Mignotte. Sebuah makalah yang bagus tentang batas tinggi dalam anjak piutang adalah Batas pada Faktor di Z [x] , John Abbott, 2009 (tautannya ke arxiv pracetak; CV-nya mengatakan bahwa itu telah diterima oleh Journal of Symbolic Computation ). Bentuk paling santai yang diberikan ada dalam hal norma L-2, tetapi untuk menghemat byte saya bersantai lebih jauh dan menggunakan norma L-1 sebagai gantinya. Maka itu kasus kekerasan paksa oleh divisi sidang.
3. Di atas bidang terbatas, setiap polinomial adalah kali konstan polinomial monik, jadi saya hanya melakukan pembagian percobaan oleh polinomial monik dan menyimpan timbal balik di bidang tersebut. Namun, Zini hanya cincin dan karenanya perlu dilakukan pembagian uji coba oleh faktor kandidat non-monik. Saya berhasil lolos dengan tidak menerapkan bilangan rasional dengan melakukan tes pembagian faktor utama dan mengumpulkan bendera "kesalahan" e.
4. Baik poin 2 dan 3 menyiratkan bahwa kasus anjak piutang Zumumnya lebih lambat, dan tidak dapat diuji dengan demo online. Namun, kasus uji resmi paling lambat membutuhkan waktu 10 menit, yang berada dalam batas waktu "wajar".