Letzte Ziffer ungleich Null eines Fakultät

Question

Letzte Ziffer ungleich Null eines Fakultät

8

Ich möchte die letzte Ziffer ungleich Null eines Faktors bestimmen.

Ich habe versucht, es zu lösen, indem ich division: Dividiere die Zahl durch 10 oder ein Vielfaches davon.

%Vor%

Also teile ich 5040 durch 10 und bekomme 4 als Ergebnis.

Aber, sagen wir, wir sollten die Zahl 7 in der Logik anstelle des Faktors (5040) verwenden.

Bitte lassen Sie mich wissen, wie kann ich es tun?

algorithm math

Mahiz 02.11.2012, 13:14

quelle

3 Antworten

Tags und Links algorithm math

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Was ist die Einheit von 'ru_maxrss' unter Linux?

score 13 · Answer 1

Berechne die Zerlegung von n! wie folgt:
- für jede Primzahl p & lt; = n , der Exponent von p ist
  $\sum_{i=1}^{p%5i\le n}{\left\lfloor\frac % 7Bn% 7D% 7Bp% 5Ei% 7D% 5Cright% 5Chrfloor% 7D$
Subtrahiere den Exponenten von 5 vom Exponenten von 2 und verwerfe alle Fünfen von der primären Dekomposition.
Multiplizieren Sie die verbleibende Prim-Dekomposition modulo 10. Beachten Sie, dass Sie dabei die folgende Äquivalenz verwenden können: $p^{i+1 % 7D% 5Cbmod% 2010% 5Cequiv% 20% 28p% 5Cbmod% 2010% 29% 5E% 7B% 28i% 5Cbmod% 204% 29% 2B1% 7D$ (für i ≥ 0). Die einzelnen Produkte können bei Bedarf auch mod 10 gemacht werden.

Ich habe ein bisschen Zeit gebraucht, um diese Lösung in bash zu implementieren. (Bash? Nun, warum nicht?):

%Vor%

Ja, der letzte ist ein Hack.

Außerdem: Es gibt eine noch bessere rekursive Lösung. Suchen Sie Ссылка oder googlen Sie selbst.

score 1 · Answer 2

Man muss mehr als 1 Zahl behalten , wenn die nächste (modifizierte) Zahl mit 5 endet.

Der erste derartige Ort kommt um 15 !, wenn 14! = 87178291200 und 2 * 15 = 30 aber 15! = 1307674368000. Stattdessen 12 * 15 = 180, was das richtige Ergebnis ergibt.

EDIT: aber sogar die Ziffern zu zwei hinzuzufügen, ist nicht genug für einen allgemeinen Fall, bei 25! man benötigt 3 letzte Ziffern von 24! = 936, um die richtige Antwort zu erhalten, was bedeutet, dass dieser Ansatz am Ende die Hitze nicht aushält.

score 1 · Answer 3

Nehmen wir an, dass D (N) die letzte nicht-Null-Stelle von faktoriell bezeichnet, dann

D (N) = 4 * D [N / 5] * D (Einerstelle von N) [Wenn eine Zehnerstelle von N ungerade ist] D (N) = 6 * D [N / 5] * D (Einheitsziffer von N) [Wenn die Zehnerstelle von N gerade ist]; Wo [N / 5] die größte Integer-Funktion ist und D (1) = 1 D (2) = 2 D (3) = 6 D (4) = 4 D (5) = 2 D (6) = 2 D (7) = 4 D (8) = 2 D ( 9) = 8

z.B. D (26) = 6 * D [26/5] * D (6) = 6 * D (5) * D (6) = 6 * 2 * 2 = 4 [D (5) bedeutet letzte Nicht-Nullstelle von 5 ! = 120, das ist 2, dasselbe für D (6)] D (33) = 4 · D [33/5] · D (3) = 4 · D (6) · D (3) = 4 · 2 · 6 = 8

Referenz: Ссылка