找到最小的X，使X！在C ++中至少包含Y尾随零

  • Z时代
  • 2024-01-10
  • 分类：综合

我们必须取一个数字Y，我们将找到最小的数字X，例如X！至少包含Y个训练零。例如，如果Y = 2，则X的值为10。=3228800。它具有Y个零。

我们可以使用二进制搜索解决此问题。N中的尾随零数！由N！中因子5的计数得出。可以使用[0，5 * Y]范围内的二进制搜索找到X

示例

#include<iostream>
using namespace std;
int factorCount(int n, int X) {
   if (X < n)
      return 0;
   return (X / n + factorCount(n, X / n));
}
int findX(int Y) {
   int left = 0, right = 5 * Y;
   int N = 0;
   while (left <= right) {
      int mid = (right + left) / 2;
   if (factorCount(5, mid) < Y) {
      left = mid + 1;
   }else {
      N = mid;
      right = mid - 1;
      }
   }
   return N;
}
int main() {
   int Y = 4;
   cout << "Smallest value of X: " << findX(Y);
}

输出结果

Smallest value of X: 20

以上是 找到最小的X，使X！在C ++中至少包含Y尾随零 的全部内容， 来源链接： utcz.com/z/316771.html

回到顶部