ภาพรวมปัญหา
สมมติว่ามีฟังก์ชัน f(x) คืนค่าจำนวนศูนย์ท้ายของ x! (แฟกทอเรียล) เช่น f(3) = 0 เพราะ 3! = 6, f(11) = 2 เพราะ 11! = 39916800 กำหนด K หาจำนวนจำนวนเต็มบวก x ที่ทำให้ f(x) = K
ตัวอย่าง
K = 2 → Output = 5 (คือ x = 10, 11, 12, 13, 14)
แนวทางแก้ปัญหา
- f(x) = จำนวนตัวคูณ 5 ใน x! = Σ floor(x/5^i)
- f(x) เป็นฟังก์ชันไม่ลด (non-decreasing)
- ใช้ Binary Search หา x น้อยสุดที่ f(x) ≥ K
- ถ้า f(x) == K คืนค่า 5 (เพราะ f(x) คงที่ในช่วง 5 ตัวติดกัน) มิฉะนั้นคืนค่า 0
ตัวอย่างโปรแกรม
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
lli ok(lli x) {
int ret = 0;
for(lli i = 5; i <= x; i *= 5) {
ret += x / i;
}
return ret;
}
int preimageSizeFZF(int K) {
if(K == 0) return 5;
lli low = 1;
lli high = (lli)K * 5;
while(low < high) {
lli mid = low + (high - low) / 2;
lli x = ok(mid);
if(x < K) low = mid + 1;
else high = mid;
}
return ok(low) == K ? 5 : 0;
}
};
int main() {
Solution ob;
cout << (ob.preimageSizeFZF(2));
}
Input
2
Output
5
