우리는 숫자 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