誰がまだこのスレッドに注意を払っているのかわかりませんが、とにかくここに行きます.
まず、公式に見えるリンクされたバージョンでは、10000 階乗ではなく、1000 階乗である必要があります。また、この問題が別のプログラミングコンテストで再利用されたとき、制限時間は 1 秒ではなく 3 秒でした。これにより、十分な速さで解決策を得るためにどれだけ努力しなければならないかが大きく異なります。
第 2 に、コンテストの実際のパラメータについては、Peter のソリューションは適切ですが、さらに 1 つのひねりを加えると、32 ビット アーキテクチャで 5 倍高速化できます。(または、1000 だけが必要な場合は 6 の因数でさえも!) つまり、個々の数字を処理する代わりに、基数 100000 で乗算を実装します。次に、最後に、各スーパー ディジット内の数字を合計します。コンテストでどれだけ優れたコンピュータを使用できたかはわかりませんが、自宅にはコンテストとほぼ同じくらい古いデスクトップがあります。次のサンプル コードでは、1000 に 16 ミリ秒かかります。10000 なら 2.15 秒！このコードでは、後続の 0 が表示されても無視されますが、節約できるのは作業の約 7% だけです。
#include <stdio.h>
int main() {
unsigned int dig[10000], first=0, last=0, carry, n, x, sum=0;
dig[0] = 1;
for(n=2; n <= 9999; n++) {
carry = 0;
for(x=first; x <= last; x++) {
carry = dig[x]*n + carry;
dig[x] = carry%100000;
if(x == first && !(carry%100000)) first++;
carry /= 100000; }
if(carry) dig[++last] = carry; }
for(x=first; x <= last; x++)
sum += dig[x]%10 + (dig[x]/10)%10 + (dig[x]/100)%10 + (dig[x]/1000)%10
+ (dig[x]/10000)%10;
printf("Sum: %d\n",sum); }
3 番目に、別のかなりの係数で計算を高速化する、驚くほど簡単な方法があります。大きな数を乗算する最新の方法では、n! の計算に 2 次時間はかかりません。代わりに、O-tilde(n) 時間で実行できます。ここで、チルダは、対数係数を投入できることを意味します。カラツバによる単純な加速がありますが、時間の複雑さはそれほど低下しませんが、それでも改善され、さらに 4 倍ほど節約できます。それを使用するには、階乗自体を同じサイズの範囲に分割する必要もあります。k から n までの数値を擬似コード式で乗算する再帰アルゴリズム prod(k,n) を作成します。
prod(k,n) = prod(k,floor((k+n)/2))*prod(floor((k+n)/2)+1,n)
次に、カラツバを使用して、結果として得られる大きな乗算を行います。
カラツバよりさらに優れているのは、フーリエ変換ベースのシェーンハーゲ シュトラッセン乗算アルゴリズムです。たまたま、どちらのアルゴリズムも最新の大きな数のライブラリの一部です。巨大な階乗を迅速に計算することは、特定の純粋数学アプリケーションにとって重要になる場合があります。Schonhage-Strassen は、プログラミング コンテストとしてはやり過ぎだと思います。カラツバは非常にシンプルで、問題に対する A+ ソリューションとして想像できます。
提起された質問の一部は、コンテストの問題を完全に変える単純な数論のトリックがあるという推測です。たとえば、質問が n! を決定する場合。mod n+1 の場合、ウィルソンの定理によれば、n+1 が素数の場合、答えは -1 であり、n=3 の場合は 2 であり、n+1 が合成の場合は 0 であることを確認するのは非常に簡単です。これにもバリエーションがあります。たとえば、n! mod 2n+1 も非常に予測可能です。合同と数字の合計の間にもいくつかの接続があります。x mod 9 の桁の合計も x mod 9 です。これが、x = n の場合、合計が 0 mod 9 になる理由です。n >= 6 の場合。x mod 11 の数字の交互の合計は、x mod 11 に等しくなります。
問題は、モジュロではなく、大きな数の桁の合計が必要な場合、数論のトリックはすぐに使い果たされることです。数字の桁の足し算は、繰り上げのある足し算や掛け算とうまく噛み合いません。高速なアルゴリズムに数学が存在しないと約束するのは難しいことがよくありますが、この場合、既知の公式はないと思います。たとえば、グーゴルの階乗の桁数の合計は、およそ 100 桁の数にすぎませんが、誰も知らないに違いありません。