Sie sollten ein Programm oder eine Funktion schreiben, die drei positive Ganzzahlen n b kals Eingabe- und Ausgabewerte enthält oder die letzten kZiffern vor den nachgestellten Nullen in der Basisdarstellung bvon zurückgibt n!.

Beispiel

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

Eingang

• 3 positive ganze Zahlen n b kwo 2 <= b <= 10.
• Die Reihenfolge der Eingangszahlen kann beliebig gewählt werden.

Ausgabe

• Eine Liste der zurückgegebenen oder als Ganzzahl oder Ganzzahlliste ausgegebenen Ziffern.
• Führende Nullen sind optional.
• Ihre Lösung muss jeden Beispieltestfall auf meinem Computer in weniger als einer Minute lösen (ich teste nur enge Fälle. Ich habe einen unterdurchschnittlichen PC.).

Beispiele

Neue Tests hinzugefügt, um die Richtigkeit der Einsendungen zu überprüfen. (Sie sind nicht Teil der Laufzeitregel unter 1 Minute.)

Eingabe => Ausgabe (mit der Wahl, führende Nullen wegzulassen)

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

Dies ist Code-Golf, also gewinnt der kürzeste Eintrag.

Dyalog APL , 23 Bytes

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

Dieses Programm funktioniert, solange die Fakultät die interne Repräsentationsgrenze nicht überschreitet. In Dyalog APL kann das Limit um erhöht werden ⎕FR←1287.

Angenommen, die Variablen n, b und k wurden gesetzt (z. B. n b k←7 5 4). Wenn Sie jedoch lieber zur Eingabe von n , b und k (in dieser Reihenfolge) auffordern möchten , ersetzen Sie die drei Zeichen durch ⎕.

Mathematica, 57 48 Bytes

9 Bytes dank @ 2012rcampion eingespart.

IntegerString[#!/#2^#!~IntegerExponent~#2,##2]&

Python, 198 192 181 Zeichen

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

Es ist schnell genug, ~ 23 Sekunden für das größte Beispiel. Und keine Fakultät eingebaut (ich sehe dich an, Mathematica!).

Pyth, 26 35 Bytes

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

Dies ist eine Funktion von 3 Argumenten, Anzahl, Basis, Anzahl der Ziffern.

Demonstration.

Der langsamste Testfall, der letzte, dauert auf meinem Computer 15 Sekunden.

PARI / GP, 43 Bytes

Die Handelsgeschwindigkeit für den Weltraum ergibt diesen einfachen Algorithmus:

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

Jeder der Testfälle läuft auf meinem Rechner in weniger als einer Sekunde.

Mathematica - 48 Bytes

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

Ungolfed:

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*)
]

Beispiel:

#!~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}} *)

In den meisten Fällen werden die Ziffern nicht durch den einschränkenden Faktor generiert:

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

Die Musterübereinstimmung scheint zu sein O(n^2), was dazu führt , dass die letzten beiden Testfälle die Ein-Minuten-Marke weit überschreiten.

Bash / Coreutils / DC, 60 Bytes

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

Verwendet das dcSkript aus meiner Antwort, um das Faktorielle zu finden , und gibt es in der Basis aus $2, sedum nachfolgende Nullen abzuschneiden und taildie letzten $3Ziffern auszuwählen .

Haskell, 111 109 Bytes

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

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

Dauert f 359221 2 40auf meinem 4 Jahre alten Laptop ungefähr 8 Sekunden .

So funktioniert es: Falte die Multiplikation ( *) in die Liste [1..n]. Konvertieren Sie jedes Zwischenergebnis in eine Basis bals Liste von Ziffern (niedrigstwertige zuerst), entfernen Sie führende Nullen, nehmen Sie dann die ersten kZiffern und konvertieren Sie erneut zur Basis 10. Zuletzt wieder in Basis konvertieren b, jedoch mit der höchstwertigen Ziffer zuerst.

Python 3, 146 Bytes

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]):])

Ich bin nicht sicher, ob die Testfälle alle schnell genug ablaufen werden - die größeren sind sehr langsam (da sie die Nummer durchlaufen).

Probieren Sie es hier online aus (aber seien Sie vorsichtig).

Java, 303 299 296 Bytes

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()));}}

Auf meinem Computer beträgt dieser Durchschnitt im 359221 2 40Testfall etwas weniger als eine Drittelsekunde. Übernimmt die Eingabe über Befehlszeilenargumente.

bc 75 Bytes

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

Dies verwendet einige GNU-Erweiterungen, um die Codegröße zu reduzieren. Ein POSIX-konformes Äquivalent wiegt 80 Byte:

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

Um die Laufzeiten angemessen zu halten, schneiden wir die nachgestellten Nullen ( while(!x%b)x/=b) ab und kürzen auf das Finalek Ziffern ( x%=b^k), während wir die Fakultät ( for(x=1;n;)x*=n--) berechnen .

Testprogramm:

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

Die Laufzeit der vollständigen Testsuite beträgt ca. 4¼ Sekunden auf meiner Workstation aus dem Jahr 2006.

PHP, 80 Bytes

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

Wird wie f(359221,2,40)für den letzten Testfall verwendet. Läuft für alle Testfälle ziemlich flüssig.

Versuch es hier !