Powinieneś napisać program lub funkcję, która podała trzy dodatnie liczby całkowite n b k
jako dane wyjściowe lub zwraca ostatnie k
cyfry przed końcowymi zerami w podstawowej b
reprezentacji 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 k
gdzie2 <= 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.
code-golf
number-theory
base-conversion
factorial
randomra
źródło
źródło
7 5 3
wypisze „013” lub „13”?7 10 4
przypadku testowego powiedziałbym13
n
lubk
? Czy możemy ograniczyć je do zakresu liczb całkowitych języka?Odpowiedzi:
Dyalog APL , 23 bajty
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⎕
.źródło
Mathematica,
5748 bajtówZaoszczędzono 9 bajtów dzięki @ 2012rcampion.
źródło
b
najpierw zapisać 2 bajty?IntegerString[#!#2^-#!~IntegerExponent~#2,##2]&
(zarówno to, jak i twój oryginał są dość szybkie)SlotSequence
sztuczka, 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ć.Python,
198192181 znakówJest wystarczająco szybki, około 23 sekund na największym przykładzie. I nie ma wbudowanego silnia (patrzę na ciebie, Mathematica!).
ź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.111973>>2*(b-2)&3
jest jeszcze krótsza. Jest to ta sama liczba bajtów dla poprzedniego (90946202>>3*(b-2)&7
).Pyth,
2635 bajtówJest to funkcja 3 argumentów, liczby, podstawy, liczby cyfr.
Demonstracja.
Najwolniejszy przypadek testowy, ostatni, zajmuje 15 sekund na moim komputerze.
źródło
PARI / GP, 43 bajty
Szybkość handlu przestrzenią daje ten prosty algorytm:
Każdy z przypadków testowych działa na moim komputerze w mniej niż sekundę.
źródło
Mathematica - 48 bajtów
Nie golfowany:
Przykład:
W największych przypadkach czynnikiem ograniczającym nie jest generowanie cyfr:
Wygląda na to
O(n^2)
, że dopasowanie wzorca powoduje, że dwa ostatnie przypadki testowe przekraczają jednominutowy znak.źródło
Bash / coreutils / dc, 60 bajtów
Używa
dc
skryptu z mojej odpowiedzi: Znajdź czynnik , wypisując go w bazie$2
,sed
aby przyciąć końcowe zera itail
wybrać ostatnie$3
cyfry.źródło
rev
sedowi, aby zmniejszyć cofanie się, ale todc
zjada procesor ...Haskell,
111109 bajtówZastosowanie:
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 40
na moim 4-letnim laptopie.Jak to działa: złóż mnożenie (
*
) na listę[1..n]
. Konwertuj każdy wynik pośredni na bazęb
jako listę cyfr (najpierw najmniej znaczącą), usuń wiodące zera, a następnie weź pierwszek
cyfry i ponownie przekonwertuj na bazę 10. Na koniecb
ponownie przekonwertuj na bazę , ale najpierw z najbardziej znaczącą cyfrą.źródło
Python 3, 146 bajtów
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).
źródło
Java,
303299296 bajtówNa moim komputerze to średnio nieco mniej niż jedna trzecia sekundy w przypadku
359221 2 40
testowym. Pobiera dane wejściowe za pomocą argumentów wiersza poleceń.źródło
bc, 75 bajtów
Wykorzystuje to niektóre rozszerzenia GNU, aby zmniejszyć rozmiar kodu; ekwiwalent zgodny z POSIX waży 80 bajtów:
Aby zachować rozsądny czas działania, przycinamy końcowe zera (
while(!x%b)x/=b
) i obcinamy do ostatnichk
cyfr (x%=b^k
) podczas obliczania silni (for(x=1;n;)x*=n--
).Program testowy:
Czas działania pełnego pakietu testowego wynosi około 4¼ sekundy na mojej stacji roboczej z rocznika 2006.
źródło
bc
program (golfowy lub nie), więc wszelkie wskazówki są szczególnie mile widziane ...PHP, 80 bajtów
Używany jak
f(359221,2,40)
w ostatnim przypadku testowym. Działa dość płynnie dla wszystkich przypadków testowych.Wypróbuj tutaj!
źródło