Ostatnie niezerowe cyfry silni w bazie

22

Powinieneś napisać program lub funkcję, która podała trzy dodatnie liczby całkowite n b kjako dane wyjściowe lub zwraca ostatnie kcyfry przed końcowymi zerami w podstawowej breprezentacji n!.

Przykład

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

Wkład

  • 3 dodatnie liczby całkowite n b kgdzie 2 <= b <= 10.
  • Kolejność liczb całkowitych wejściowych można wybrać dowolnie.

Wydajność

  • Lista cyfr zwróconych lub wyprowadzonych jako liczba całkowita lub lista liczb całkowitych.
  • Zera wiodące są opcjonalne.
  • Twoje rozwiązanie musi rozwiązać każdy przykładowy przypadek testowy w ciągu minuty na moim komputerze (przetestuję tylko zamknięte przypadki. Mam komputer poniżej średniej.)

Przykłady

Dodano nowe testy w celu sprawdzenia poprawności zgłoszeń. (Nie są objęte regułą czasu działania poniżej 1 minuty.)

Dane wejściowe => Dane wyjściowe (z możliwością pominięcia początkowych zer)

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

To jest golf golfowy, więc wygrywa najkrótszy wpis.

randomra
źródło
1
na minutę na moim komputerze trudno jest celować, jeśli nie znamy żadnych szczegółów.
Dennis
1
Czy 7 5 3wypisze „013” lub „13”?
Claudiu
1
@Claudiu na podstawie 7 10 4przypadku testowego powiedziałbym13
Maltysen
2
@Claudiu „Zera wiodące są opcjonalne”. więc obie wersje są poprawne.
randomra
1
Musimy przyjąć dowolną liczbą całkowitą dodatnią dla nlub k? Czy możemy ograniczyć je do zakresu liczb całkowitych języka?
Toby Speight

Odpowiedzi:

1

Dyalog APL , 23 bajty

⌽k↑⌽{⍵↓⍨-⊥⍨0=⍵}b⊥⍣¯1⊢!n

Ten program działa tak długo, jak silnia nie przekracza wewnętrznego limitu reprezentacji. W Dyalog APL limit można podnieść o ⎕FR←1287.

Zakłada się, że zmienne n, b i k zostały ustawione (np. n b k←7 5 4), Ale jeśli wolisz monitować o n , b i k (w tej kolejności), zamień trzy znaki na .

Adám
źródło
Każdy przypadek testowy, na który rzuciłem, był obliczany na mojej maszynie w około 11 mikrosekund (M540).
Adám
7

Mathematica, 57 48 bajtów

Zaoszczędzono 9 bajtów dzięki @ 2012rcampion.

IntegerString[#!/#2^#!~IntegerExponent~#2,##2]&
alephalpha
źródło
Nigdy tak naprawdę nie używałem matematyki, ale czy nie mógłbyś zamienić kolejności argumentów, aby bnajpierw zapisać 2 bajty?
FryAmTheEggman
@FryAmTheEggman Jestem nowy w społeczności golfistów, czy zamienianie argumentów na „koszerne”?
2012rcampion
1
Możesz dostać się do 47: IntegerString[#!#2^-#!~IntegerExponent~#2,##2]&(zarówno to, jak i twój oryginał są dość szybkie)
2012rcampion
Pytający napisał: „Kolejność liczb całkowitych wejściowych można wybrać dowolnie”. pod wejściem, więc w tym przypadku jest zdecydowanie w porządku
FryAmTheEggman
@Fry Wow, wygląda na to, że nie czytałem wystarczająco blisko. Jednak SlotSequencesztuczka, której użyłem w moim komentarzu, działa tylko z bieżącym zamówieniem, więc nie możesz już więcej zapisać.
2012rcampion
7

Python, 198 192 181 znaków

def F(n,b,k):
 p=5820556928/8**b%8;z=0;e=f=x=1
 while n/p**e:z+=n/p**e;e+=1
 z/=1791568/4**b%4;B=b**(z+k)
 while x<=n:f=f*x%B;x+=1
 s='';f/=b**z
 while f:s=str(f%b)+s;f/=b
 return s

Jest wystarczająco szybki, około 23 sekund na największym przykładzie. I nie ma wbudowanego silnia (patrzę na ciebie, Mathematica!).

Keith Randall
źródło
[2,3,2,5,3,7,2,3,5][b-2]może być int('232537235'[b-2])zapisanie 3 bajtów. [1,1,2,1,1,1,3,2,1][b-2]podobnie.
randomra
W tym drugim przypadku tabela odnośników 111973>>2*(b-2)&3jest jeszcze krótsza. Jest to ta sama liczba bajtów dla poprzedniego ( 90946202>>3*(b-2)&7).
Sp3000
nvm wygląda na to, że miałeś rację w kwestii wyższych cyfr
Sp3000
Wierzę, że możesz zaoszczędzić kilka bajtów, tworząc program, a nie funkcję.
FryAmTheEggman
6

Pyth, 26 35 bajtów

M?G%GHg/GHH.N>ju%g*GhHT^T+YslNN1T_Y

Jest to funkcja 3 argumentów, liczby, podstawy, liczby cyfr.

Demonstracja.

Najwolniejszy przypadek testowy, ostatni, zajmuje 15 sekund na moim komputerze.

isaacg
źródło
@ Sp3000 Dodałem poprawkę, która moim zdaniem powinna wystarczyć.
isaacg
2

PARI / GP, 43 bajty

Szybkość handlu przestrzenią daje ten prosty algorytm:

(n,b,k)->digits(n!/b^valuation(n!,b)%b^k,b)

Każdy z przypadków testowych działa na moim komputerze w mniej niż sekundę.

Charles
źródło
2

Mathematica - 48 bajtów

#!~IntegerDigits~#2/.{l__,0...}:>{l}~PadLeft~#3&

Nie golfowany:

Function[{n, b, k},
  IntegerDigits[n!, b] (* list of the base-b digits in n! *)
  /. {l__, 0...} (* match a sequence of elements l and some number of zeros*)
                 (* lucky for me, __ defaults to match the shortest number *)
     :> PadLeft[List[l], k] (* pad l to be k elements long with zeros on the left *)
                            (* this truncates the list if it is too long*)
]

Przykład:

#!~IntegerDigits~#2/.{l__,0...}:>{l}~PadLeft~#3 &
%[758, 9, 19] // Timing

(* {0.031250, {6, 6, 4, 5, 0, 0, 2, 3, 0, 2, 2, 1, 7, 5, 3, 7, 8, 6, 3}} *)

W największych przypadkach czynnikiem ograniczającym nie jest generowanie cyfr:

Length@IntegerDigits[359221!, 2] // Timing
(* {0.109375, 6111013} 6.1M digits in 100 ms *)

Wygląda na to O(n^2), że dopasowanie wzorca powoduje, że dwa ostatnie przypadki testowe przekraczają jednominutowy znak.

2012 rcampion
źródło
2

Bash / coreutils / dc, 60 bajtów

dc<<<"1 `seq -f%g* $1`$2op"|sed -r s/0+$//|tail -c$(($3+1))

Używa dcskryptu z mojej odpowiedzi: Znajdź czynnik , wypisując go w bazie $2, sedaby przyciąć końcowe zera i tailwybrać ostatnie $3cyfry.

Toby Speight
źródło
Muszę przyznać, że jest to bardzo powolne z 40-bitową testową bazą base-2. Próbowałem ułatwić pracę revsedowi, aby zmniejszyć cofanie się, ale to dczjada procesor ...
Toby Speight
2

Haskell, 111 109 bajtów

import Data.Digits
f n b k=digits b$foldl(((unDigits b.reverse.take k.snd.span(<1).digitsRev b).).(*))1[1..n]

Zastosowanie: f 158596 8 20->[3,7,2,1,2,4,7,6,7,0,0,4,4,2,2,5,4,6,1,4]

Trwa około 8 sekund f 359221 2 40na moim 4-letnim laptopie.

Jak to działa: złóż mnożenie ( *) na listę [1..n]. Konwertuj każdy wynik pośredni na bazę bjako listę cyfr (najpierw najmniej znaczącą), usuń wiodące zera, a następnie weź pierwsze kcyfry i ponownie przekonwertuj na bazę 10. Na koniec bponownie przekonwertuj na bazę , ale najpierw z najbardziej znaczącą cyfrą.

nimi
źródło
miałeś w głowie pomysł, że interpretuję to za pomocą Matlaba, co za zbieg okoliczności: D
Abr001am
1

Python 3, 146 bajtów

import math
i,f=input(),int
n=i.split()
e=math.factorial(f(n[0]))
d=''
while e>0:
 d=str((e%f(n[1])))+d;e=e//f(n[1])
print(d.strip('0')[-f(n[2]):])

Nie jestem pewien, czy wszystkie przypadki testowe będą działać wystarczająco szybko - większe są bardzo wolne (ponieważ pętla przechodzi przez liczbę).

Wypróbuj online tutaj (ale bądź ostrożny).

Tim
źródło
1

Java, 303 299 296 bajtów

import java.math.*;interface R{static void main(String[]a){BigInteger c=new BigInteger(a[1]),b=c.valueOf(1);for(int i=new Integer(a[0]);i>0;i--){b=b.multiply(b.valueOf(i));while(b.mod(c).equals(b.ZERO))b=b.divide(c);b=b.mod(c.pow(new Integer(a[2])));}System.out.print(b.toString(c.intValue()));}}

Na moim komputerze to średnio nieco mniej niż jedna trzecia sekundy w przypadku 359221 2 40testowym. Pobiera dane wejściowe za pomocą argumentów wiersza poleceń.

SuperJedi224
źródło
1

bc, 75 bajtów

define void f(n,b,k){
obase=b
for(x=1;n;x%=b^k){
x*=n--
while(!x%b)x/=b}
x}

Wykorzystuje to niektóre rozszerzenia GNU, aby zmniejszyć rozmiar kodu; ekwiwalent zgodny z POSIX waży 80 bajtów:

define f(n,b,k){
obase=b
for(x=1;n;x%=b^k){
x*=n--
while(x%b==0)x/=b}
return(x)}

Aby zachować rozsądny czas działania, przycinamy końcowe zera ( while(!x%b)x/=b) i obcinamy do ostatnich kcyfr ( x%=b^k) podczas obliczania silni ( for(x=1;n;)x*=n--).

Program testowy:

f(3, 10, 1)
f(7, 5, 4)
f(3, 2, 3)
f(6, 2, 10)
f(9, 9, 6)
f(7, 10, 4)
f(758, 9, 19)
f(158596, 8, 20)
f(359221, 2, 40)
f(9, 6, 3)
f(10, 6, 3)
quit

Czas działania pełnego pakietu testowego wynosi około 4¼ sekundy na mojej stacji roboczej z rocznika 2006.

Toby Speight
źródło
To mój pierwszy bcprogram (golfowy lub nie), więc wszelkie wskazówki są szczególnie mile widziane ...
Toby Speight,
0

PHP, 80 bajtów

function f($a,$b,$c){echo substr(rtrim(gmp_strval(gmp_fact($a),$b),"0"),-1*$c);}

Używany jak f(359221,2,40)w ostatnim przypadku testowym. Działa dość płynnie dla wszystkich przypadków testowych.

Wypróbuj tutaj!

Paul Picard
źródło