n！となるようなxの最大値を見つけます。 ％（k ^ x）=0（C ++の場合）

2つの整数nとkがあるとします。 n！のようなxの最大値を見つける必要があります。 mod（k ^ x）=0。したがって、n =5、k =2の場合、出力は3になります。Asn！ =120、xの値が異なると、次のようになります-

120 mod 2 ^ 0 =0、120 mod 2 ^ 1 =0、120 mod 2 ^ 2 =0、120 mod 2 ^ 3 =0、120 mod 2 ^ 4 =8、120 mod 2 ^ 5 =24、120 mod 2 ^ 6 =56、120 mod 2 ^ 7=120。x=3の最大値として、結果は0であるため、出力は3です。

これを解決するには、次の手順に従う必要があります-

• kの平方根を取り、mに保存します
• i：=2からmの場合、次の手順を実行します。
  • i =mの場合、i：=kを設定します
  • kがiで割り切れる場合は、kをiで割ります
  • nまでループを実行し、uという変数に商を追加します。
  • 各ループの後に、rの最小値を保存します

例

#include <iostream>
#include <cmath>
using namespace std;
int calculateMaxX(int n, int k) {
   int result = n, v, u;
   int m = sqrt(k) + 1;
   for (int i = 2; i <= m && k > 1; i++) {
      if (i == m) {
         i = k;
      }
      for (u = v = 0; k % i == 0; v++) {
         k /= i;
      }
      if (v > 0) {
         int t = n;
         while (t > 0) {
            t /= i;
            u += t;
         }
         result = min(result, u / v);
      }
   }
   return result;
}
int main() {
   int n = 5;
   int k = 2;
   cout<<"Maximum value of x is: " << calculateMaxX(n, k);
}

出力

Maximum value of x is: 3