求x的最大值，使n！％（k ^ x）= 0在C ++中

假设我们有两个整数n和k。我们必须找到x的最大值，使得n！mod（k ^ x）=0。因此，当n = 5且k = 2时，输出将为3。= 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