Tìm số X nhỏ nhất sao cho X! chứa ít nhất Y số 0 ở cuối trong C ++

Chúng ta phải lấy một số Y, chúng ta sẽ tìm được số X nhỏ nhất, sao cho X! chứa ít nhất Y số lượng 0 huấn luyện. Ví dụ, nếu Y =2, thì giá trị của X =10. As X! =3228800. Nó có Y là số không.

Chúng tôi có thể giải quyết điều này bằng cách sử dụng tìm kiếm nhị phân. Số lượng các số không ở cuối trong N! được cho bởi số lượng các thừa số 5 trong N !. X có thể được tìm thấy bằng cách sử dụng tìm kiếm nhị phân trong phạm vi [0, 5 * Y]

Ví dụ

#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);
}

Đầu ra

Smallest value of X: 20