Você deve escrever um programa ou função que tenha fornecido três números inteiros positivos n b k
como saída ou retorne os últimos k
dígitos antes dos zeros à direita na b
representação base de n!
.
Exemplo
n=7 b=5 k=4
factorial(n) is 5040
5040 is 130130 in base 5
the last 4 digits of 130130 before the trailing zeros are 3013
the output is 3013
Entrada
- 3 inteiros positivos
n b k
onde2 <= b <= 10
. - A ordem dos números inteiros de entrada pode ser escolhida arbitrariamente.
Saída
- Uma lista de dígitos retornados ou emitidos como um número inteiro ou lista inteira.
- Os zeros à esquerda são opcionais.
- Sua solução precisa resolver qualquer exemplo de caso de teste em menos de um minuto no meu computador (apenas testarei casos encerrados. Tenho um PC abaixo da média.).
Exemplos
Novos testes adicionados para verificar a exatidão dos envios. (Eles não fazem parte da regra de tempo de execução com menos de 1 minuto.)
Entrada => Saída (com a opção de omitir zeros à esquerda)
3 10 1 => 6
7 5 4 => 3013
3 2 3 => 11
6 2 10 => 101101
9 9 6 => 6127
7 10 4 => 504
758 9 19 => 6645002302217537863
158596 8 20 => 37212476700442254614
359221 2 40 => 1101111111001100010101100000110001110001
New tests:
----------
9 6 3 => 144
10 6 3 => 544
Isso é código-golfe, então a entrada mais curta vence.
code-golf
number-theory
base-conversion
factorial
randomra
fonte
fonte
7 5 3
"013" ou "13"?7 10 4
caso de teste eu diria13
n
ouk
? Ou podemos limitá-los ao intervalo do tipo inteiro do idioma?Respostas:
Dyalog APL , 23 bytes
Este programa funciona desde que o fatorial não exceda o limite de representação interna. No Dyalog APL, o limite pode ser aumentado por
⎕FR←1287
.Assume as variáveis n, b, e k foram definidos (por exemplo
n b k←7 5 4
), mas se você prefere deseja solicitar n , b , e k (nessa ordem), em seguida, substituir os três personagens com⎕
.fonte
Mathematica,
5748 bytesEconomizou 9 bytes graças a @ 2012rcampion.
fonte
b
primeiro salvar 2 bytes?IntegerString[#!#2^-#!~IntegerExponent~#2,##2]&
(tanto isso e seu original são bastante rápido)SlotSequence
truque que usei no meu comentário funciona apenas com o pedido atual, portanto você não pode mais salvar.Python,
198192181 caracteresÉ rápido o suficiente, ~ 23 segundos no maior exemplo. E nenhum fatorial embutido (estou olhando para você, Mathematica!).
fonte
[2,3,2,5,3,7,2,3,5][b-2]
pode serint('232537235'[b-2])
para salvar 3 bytes.[1,1,2,1,1,1,3,2,1][b-2]
similarmente.111973>>2*(b-2)&3
é ainda mais curta. É o mesmo número de bytes para o primeiro (90946202>>3*(b-2)&7
).Pitão,
2635 bytesEsta é uma função de 3 argumentos, número, base, número de dígitos.
Demonstração.
O caso de teste mais lento, o final, leva 15 segundos na minha máquina.
fonte
PARI / GP, 43 bytes
A velocidade de negociação do espaço produz este algoritmo simples:
Cada um dos casos de teste é executado em menos de um segundo na minha máquina.
fonte
Mathematica - 48 bytes
Ungolfed:
Exemplo:
Para os casos maiores, o fator limitante não está gerando os dígitos:
A correspondência de padrões parece ser
O(n^2)
, fazendo com que os dois últimos casos de teste ultrapassem a marca de um minuto.fonte
Bash / coreutils / dc, 60 bytes
Usa o
dc
script da minha resposta para Encontrar o fatorial , emitindo na base$2
, comsed
para aparar zerostail
à direita e selecionar os últimos$3
dígitos.fonte
rev
para reduzir recuo, mas édc
que está comendo a CPU ...Haskell,
111109 bytesUso:
f 158596 8 20
->[3,7,2,1,2,4,7,6,7,0,0,4,4,2,2,5,4,6,1,4]
Demora cerca de 8 segundos
f 359221 2 40
no meu laptop de 4 anos.Como funciona: dobre a multiplicação (
*
) na lista[1..n]
. Converta todos os resultados intermediários em baseb
como uma lista de dígitos (menos significativos primeiro), retire os zeros à esquerda, pegue os primeirosk
dígitos e converta na base 10 novamente. Por fim, convertab
novamente na base , mas primeiro com o dígito mais significativo.fonte
Python 3, 146 bytes
Não tenho certeza de que todos os casos de teste serão executados com rapidez suficiente - os maiores são muito lentos (pois estão repetindo o número).
Experimente online aqui (mas tenha cuidado).
fonte
Java,
303299296 bytesNo meu computador, isso fica em média um pouco menos de um terço de segundo no
359221 2 40
testcase. Recebe entrada por meio de argumentos de linha de comando.fonte
bc, 75 bytes
Isso usa algumas extensões GNU para reduzir o tamanho do código; um equivalente em conformidade com POSIX pesa 80 bytes:
Para manter os tempos de execução razoáveis, recortamos os zeros à direita (
while(!x%b)x/=b
) e truncamos para osk
dígitos finais (x%=b^k
) à medida que calculamos o fatorial (for(x=1;n;)x*=n--
).Programa de teste:
O tempo de execução do conjunto completo de testes é de aproximadamente 4 segundos na minha estação de trabalho vintage de 2006.
fonte
bc
programa (golfe ou não), de modo que qualquer dicas são especialmente bem-vindas ...PHP, 80 bytes
Usado como
f(359221,2,40)
para o último caso de teste. É executado sem problemas em todos os casos de teste.Tente aqui!
fonte