任意の数体系で階乗数の末尾のゼロを数える

特定の数値システムで数値の階乗の末尾のゼロの数を計算するにはどうすればよいですか？

10番目の数体系にある場合を見てみましょう。そして、これを普遍的なソリューションに一般化する方法を見てみましょう。 数Nが与えられ、その階乗のために、後続ゼロの数を見つける必要があります。 解決策は非常に簡単です-合計：

Math.floor(N/5) + Math.floor(N/25) + Math.floor(N/125) + Math.floor(N/625) + ...
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このような式に一般化できます：

$$

$$\ sum \ limits_ {i = 1} ^ \ infty {N \ over 5 ^ i}。$$

なぜ5？ 簡単です。 最終ゼロは、階乗の数が10の場合にのみ取得されるため、階乗の10の数を数えると、有限のゼロの数がわかります。



上の例でなぜ5で割るのですか？ 5に2を掛けると10が得られるため、完全なソリューションには2つの式があります。

$$

$$\ sum \ limits_ {i = 1} ^ \ infty {N \ over 5 ^ i}$$

そして

$$

$$\ sum \ limits_ {i = 1} ^ \ infty {N \ over 2 ^ i}。$$

しかし、論理的に推論すると、最初の金額が少なくなることがわかっているので、計算するだけです（詳細については、 こちらを参照してください）。

問題の解決策

特定の数値システムの数値の階乗の最終ゼロを計算するために、以下のアルゴリズムをコンパイルしました。

1. 番号システムの番号Bを因数分解します。
2. 数Nを各一意の素因数Kで除算し、K自体を $$$N \ K以$ 各結果をより小さな整数に丸めながら、複数あります。
3. 数体系の数を拡張するときに、いくつかの同一の素因数Kが得られる場合、上記の結果を同一のKの数で割る必要があります。
4. 一意の各因子KによるNのすべての除算のうち、最小の商を選択します。これが答えとなります。

例で示します。

数N = 5、数体系B = 12とします。階乗5！ = 120、および12番目のシステムの120はA0です。 有限数体系では、元の数の階乗には1つのゼロがあることがわかります。 12を素因数に分解すると、2、2、3が得られます。2と3の2つの一意の数値があります。アルゴリズムに従って、ポイント2を数値2で満たします。

$$

$${5 \ 2以上} + {5 \ 4以上} + {5 \ 8以上} + ... = 2 + 1 + 0 + ... = 3$$

しかし、デュースは12の分解で2回出会ったので、最終結果を2で除算し、より小さい整数に丸めます。 その結果、1が得られます。



同じことを3で行います。

$$

$${5 \ 3以上} + {5 \ 9以上} + ... = 1 + 0 + ... = 1$$

したがって、数体系の数の素因数による数Nの除算の2つの商が得られました。 どちらも1に等しいので、小さい方を選択する必要はありません。答えは1です。



別の例を考えてみましょう。



数N = 16、数体系B = 16とする。階乗16！ = 20922789888000、16番目のシステムの20922789888000-130777758000。最終的な数値システムでは、元の数値の階乗に3つのゼロがあることがわかります。 16を素因数に分解すると、2、2、2、2になります。ここでは一意の番号が1つしかないため、アイテム2は1回だけ実行されます。

$$

$${16 \ 2以上} + {16 \ 4以上} + {16 \ 8以上} + {16 \ 16以上} + {16 \ 32以上} + ... = 8 + 4 + 2 + 1 + 0 + ... = 15$$

分解すると4つのデュースが得られたため、除算の合計を4で除算し、より小さい整数に丸めます。 $$${15 \ over 4} = 3$



PS投稿の資料のほとんどはここから翻訳されています 。 Aditya Rameshによる投稿。