เราต้องใช้ตัวเลข Y เราจะหาจำนวน X ที่น้อยที่สุด เช่น X! มีจำนวนศูนย์การฝึกอย่างน้อย Y ตัวอย่างเช่น ถ้า Y =2 ค่าของ X =10 เป็น X! =3228800 มีจำนวนศูนย์ Y
เราสามารถแก้ไขได้โดยใช้การค้นหาแบบไบนารี จำนวนศูนย์ต่อท้ายใน N! ถูกกำหนดโดยการนับปัจจัย 5 ใน N! 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
