Nの基数B表現で後続ゼロの数を見つけます！ C++を使用する

この記事では、階乗のベースB表現で特定の数Nの後続ゼロを見つける問題を理解します。例

Input : N = 7 Base = 2
Output : 4
Explanation : fact(7) = 5040 in base10 and 1001110110000 in base16 having 4 trailing zero.

Input : N = 11 Base = 5
Output : 2
Explanation : fact(11) = 39916800 in base10 and 40204314200 in base16 having 2 trailing zeroes.

まず、10進数を1つの基数から別の基数に変換するプロセスを要約します。 （5040）10を（？）2に変換する例を見てみましょう

つまり、数値を2で除算し、数値をそれ以上除算できなくなるまで余りを保持します。結果は逆の順序で残りになります。

その結果、4つの後続ゼロがあり、2で数値を余り0で割ったときに得られるこの後続ゼロ。

5040の素因数分解=24* 56711 * 3381 * 181は、2が5040を4回除算し、余り0が後続ゼロに等しいことを意味します。このようにして、後続ゼロの数を計算できます。

解決策を見つけるためのアプローチ

末尾のゼロの数を見つける方法については、上記で説明しました。階乗NでBの最大の累乗を見つける必要があります。たとえば、ベースB =14の場合、ベース14の14は10として表されます。つまり、（14）10 =（10）14です。ルジャンドルの公式としても知られています。

上記のアプローチのC++コード

これが、与えられた問題を解決するための入力として使用できるC++構文です-

例

#include <bits/stdc++.h>
using namespace std;

vector < pair < int, int >> primeFactorsofBase(int Base) {
   // declaring factors to store prime factors
   // along with occurence in factorisation of Base .
   vector < pair < int, int >>factors;

   for (int i = 2; Base != 1; i++) {
      if (Base % i == 0) {
         int count = 0;
         while (Base % i == 0){
            Base = Base / i;
            count++;
         }

         factors.push_back (make_pair (i, count));
      }
   }
   return factors;
}


int main () {
   int N = 11, Base = 5;
   // finding the largest power of Base that divides factorial N.
   vector < pair < int, int >>prime_factors;
   // finding prime factors by primeFactorsofBase() function.
   prime_factors = primeFactorsofBase(Base);

   int result = INT_MAX;
   for (int i = 0; i < prime_factors.size (); i++) {
      // calculating minimum power.
      int count = 0;
      int r = prime_factors[i].first;
      while (r <= N){
         count += (N / r);
         r = r * prime_factors[i].first;
      }
      result = min (result, count / prime_factors[i].second);
   }
   //printing trailing zeroes stored in result.
   cout << "Number of trailing zeroes: " <<result;
   return 0;
}

出力

Number of trailing zeroes: 2

上記のコードの説明

• ベクトルを使用してBaseの最大の累乗を見つけます。
• 最大のべき乗を計算するには、すべての素因数を格納するベクトルを使用して素因数を計算します。
• 次に、Baseのすべての素因数の最小パワーを計算します。
• 最後に、結果を印刷します。

結論

この記事では、階乗NのベースB表現で後続ゼロの数を見つける問題を解決します。これは、ルジャンドルの公式を使用して解決します。同じ問題を解決するためにC++コードも記述します。このコードは、Java、C、Pythonなどの他の言語で記述できます。この記事がお役に立てば幸いです。