Sem usar nenhuma função interna de fatoração / polinômio, fatore um polinômio completamente em irredutíveis sobre os números inteiros ou em um campo finito.
Entrada
Seu programa / função receberá algum número primo (ou zero) n
como entrada. O campo / anel é o campo finito dessa ordem (ou seja Z/nZ
), ou apenas Z
se n
for 0
. Seu programa pode falhar se n
não for 0
ou for primo. O polinômio será inserido F[x]
.
Seu programa / função também receberá o polinômio como entrada.
Há alguma flexibilidade na entrada, certifique-se de especificar como você pretende receber entrada. Por exemplo, o polinômio pode ser inserido como uma lista de coeficientes, ou na forma que a maioria das pessoas espera (ex:) 50x^3 + x^2
, ou em alguma outra forma razoável. Ou o formato de entrada do campo / toque também pode ser diferente.
Saída
Seu programa / função produzirá o polinômio fatorado completamente. Você pode deixar várias raízes expandidas (ou seja, em (x + 1)(x + 1)
vez de (x + 1)^2
). Você pode remover o espaço em branco entre operadores binários. Você pode substituir a justaposição por *
. Você pode inserir espaços em branco em lugares estranhos. Você pode reorganizar os fatores na ordem que desejar. O x
termo poderia ser apenas (x)
. x
pode ser escrito como x^1
; no entanto, o termo constante pode não ter x^0
. +
Sinais estranhos são permitidos. Você pode não ter um termo com um 0
na frente, eles devem ser deixados de fora. O termo principal de cada fator deve ser positivo, os sinais negativos devem estar fora.
Nos casos de teste, seu programa deve ser capaz de produzir saída para cada um deles em tempo razoável (por exemplo, <= 2 horas):
Entrada: 2, x^3 + x^2 + x + 1
Saída: (x + 1)^3
Entrada: 0, x^3 + x^2 + x + 1
Saída: (x + 1)(x^2 + 1)
Entrada: 0, 6x^4 – 11x^3 + 8x^2 – 33x – 30
Saída: (3x + 2)(2x - 5)(x^2 + 3)
Entrada: 5, x^4 + 4x^3 + 4x^2 + x
Saída: x(x + 4)(x + 4)(x + 1)
Entrada: 0, x^5 + 5x^3 + x^2 + 4x + 1
Saída: (x^3 + 4x + 1)(x^2 + 1)
Agradecimentos especiais a Peter Taylor por criticar meus casos de teste
p
possui os elementos{0, 1, ... , p-1}
e está sob o modo de adição / multiplicaçãop
. Basicamente, reduza qualquer coeficiente por modp
e você é bom. Além disso, observe que, se tiver uma raiz, ou seja, um fator linear, um dos dois{0, ... , p-1}
produzirá0
(modp
) quando estiver conectado ao polinômio.Z
é fatorarZ/pZ
para ump
elevador adequado e depois Hensel. No entanto, a abordagem do jogo de golfe provavelmente é (e certamente esse é o caminho que estou vendo) usar um limite simples na altura dos fatores e força bruta.Respostas:
GolfScript (222 bytes)
Demonstração online
Notas
n
seguido por uma matriz de coeficientes GolfScript do mais ao menos significativo. Por exemplo,0, x^5 + 5x^3 + x^2 + 4x + 1
deve ser formatado como0 [1 0 5 1 4 1]
.Z
. Eu manejoZ
usando uma forma relaxada da altura de Mignotte. Um ótimo artigo sobre limites de altura na fatoração é o Bounds on Factors in Z [x] , John Abbott, 2009 (o link é para a pré-impressão arxiv; seu currículo diz que foi aceito pelo Journal of Symbolic Computation ). A forma mais relaxada dada existe em termos da norma L-2, mas para economizar bytes, relaxo ainda mais e uso a norma L-1. Então é um caso de força bruta pela divisão de julgamento.Z
é apenas um anel e, portanto, é necessário fazer a divisão do teste por fatores candidatos não-monônicos. Consigo evitar a implementação de números racionais, realizando um teste de divisão de fatores e acumulando um sinalizador de "erro"e
.Z
é geralmente mais lento e não pode ser testado com a demonstração online. No entanto, o mais lento dos casos de teste oficiais leva 10 minutos, o que está dentro do prazo "razoável".fonte