c++ - n の最後のゼロの数を見つけます!

Question

n の最後にあるゼロの数を計算する効率的な方法はありますか? n!? を明示的に計算する必要はありません。

score 5 · Accepted Answer

はいあります。重要なアイデア: (1) n! を割る最大の 5 の累乗と同じです。(2) これは、n までの 5 の倍数に、n までの 25 の倍数を加え、n までの 125 の倍数を加えたものです。

しかし、これはスタックオーバーフローには属しません。

score 3 · Accepted Answer

N! の末尾のゼロの数によって与えられます

∑ floor( n/5 ⁱ ) for i = 1,2,3....

C の単純なコード

    i = 1, sum = 0;
    while(pow(5,i)<= n)
    {
        sum += n/(pow(5,i));
        i++;
    }

score 2 · Accepted Answer

n! の 10 進数表現のゼロの数。は、その大きな数の因数として 10 が現れる回数です。したがって、2x5 が表示される回数です。したがって、因数として 5 よりも 2 の方がはるかに多く発生するため (なぜでしょうか?)、これは 5 が n! の因数である回数です。

あなたのインタビューの質問は次のとおりです。

1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x ... x (n-1) x n

?

3 に答える 3