Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

X가 되는 가장 작은 수 X를 찾으십시오! C++에서 최소한 Y개의 후행 0을 포함합니다.

<시간/>

우리는 숫자 Y를 취해야 합니다. 우리는 X와 같은 가장 작은 숫자 X를 찾을 것입니다! 최소한 Y개의 훈련 0을 포함합니다. 예를 들어, Y =2이면 X의 값은 10입니다. X로! =3228800. Y개의 0이 있습니다.

이진 검색을 사용하여 이 문제를 해결할 수 있습니다. N에서 후행 0의 수! N!의 인수 5를 세어 나타냅니다. X는 범위 [0, 5*Y]

에서 이진 검색을 사용하여 찾을 수 있습니다.

예시

#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