Link zum ursprünglichen Problem

Es ist keine Hausaufgabe. Ich dachte nur, dass jemand eine echte Lösung für dieses Problem kennen könnte.

Ich war 2004 bei einem Programmierwettbewerb und es gab folgendes Problem:

Wenn n gegeben ist, finde die Summe der Ziffern von n !. n kann zwischen 0 und 10000 liegen. Zeitlimit: 1 Sekunde. Ich denke, es gab bis zu 100 Nummern für jeden Testsatz.

Meine Lösung war ziemlich schnell, aber nicht schnell genug, sodass ich sie einige Zeit laufen ließ. Es wurde ein Array von vorberechneten Werten erstellt, die ich in meinem Code verwenden konnte. Es war ein Hack, aber es hat funktioniert.

Aber es gab einen Typ, der dieses Problem mit ungefähr 10 Codezeilen löste und es würde in kürzester Zeit eine Antwort geben. Ich glaube, es war eine Art dynamisches Programmieren oder etwas aus der Zahlentheorie. Wir waren damals 16 Jahre alt, es sollte also keine "Raketenwissenschaft" sein.

Weiß jemand, welche Art von Algorithmus er verwenden könnte?

BEARBEITEN: Es tut mir leid, wenn ich die Frage nicht klar gestellt habe. Wie Mquander sagte, sollte es eine clevere Lösung ohne Fehler geben, mit einfachem Pascal - Code, ein paar Schleifen, O (n2) oder sowas ähnliches. 1 Sekunde ist keine Einschränkung mehr.

ich fandHier dass, wenn n> 5, dann 9 die Summe der Ziffern einer Fakultät teilt. Wir können auch feststellen, wie viele Nullen am Ende der Zahl stehen. Können wir das benutzen?

Ok, ein weiteres Problem vom Programmierwettbewerb aus Russland. Bei 1 <= N <= 2 000 000 000 wird N ausgegeben! mod (N + 1). Ist das irgendwie verwandt?