สมมติว่าเรามีฟังก์ชัน f(x) ซึ่งจะคืนค่าจำนวนศูนย์ที่ส่วนท้ายของแฟคทอเรียลของ x ดังนั้นสำหรับ f(3) =0 เพราะ 3! =6 ไม่มีเลขศูนย์ต่อท้าย ในขณะที่ f(11) =2 เพราะ 11! =39916800 มีศูนย์ 2 ตัวต่อท้าย ตอนนี้เมื่อเรามี K เราต้องหาจำนวนเต็มที่ไม่เป็นลบ x มีคุณสมบัติที่ f(x) =K
ดังนั้นหากอินพุตเป็น K =2 คำตอบจะเป็น 5
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน ok() ซึ่งจะใช้ x
- ret :=0
- สำหรับการเริ่มต้น i :=5 เมื่อฉัน <=x อัปเดต i :=i * 5 ทำ −
- ret :=ret + x / i
- คืนสินค้า
- จากวิธีหลัก ให้ทำดังต่อไปนี้ −
- ถ้า K เท่ากับ 0 แล้ว −
- คืน 5
- ต่ำ :=1 สูง :=K * 5
- ในขณะที่ต่ำ <สูง ทำ −
- กลาง :=ต่ำ + (สูง - ต่ำ) /2
- x :=โอเค(กลาง)
- ถ้า x
- ต่ำ :=กลาง + 1
- มิฉะนั้น
- สูง :=กลาง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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;
}
};
main(){
Solution ob;
cout << (ob.preimageSizeFZF(2));
} อินพุต
2
ผลลัพธ์
5
