Kích thước hình ảnh trước của hàm số không giai thừa trong C ++

Giả sử chúng ta có một hàm f (x), điều này sẽ trả về số lượng các số 0 ở cuối giai thừa của x. Vì vậy, cho f (3) =0 vì 3! =6 không có số 0 ở cuối, trong khi f (11) =2 vì 11! =39916800 có 2 số 0 tận cùng. Bây giờ khi chúng ta có K, chúng ta phải tìm xem có bao nhiêu số nguyên không âm x có tính chất f (x) =K.

Vì vậy, nếu đầu vào là K =2, thì câu trả lời sẽ là 5.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một hàm ok (), điều này sẽ lấy x,
• ret:=0
• để khởi tạo i:=5, khi i <=x, cập nhật i:=i * 5, thực hiện -
  • ret:=ret + x / i
• trả lời lại
• Từ phương pháp chính, hãy thực hiện như sau -
• nếu K giống 0, thì -
  • trả về 5
• thấp:=1, cao:=K * 5
• while low
• giữa:=low + (cao - thấp) / 2
• x:=ok (giữa)
• nếu x
• thấp:=giữa + 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

2

Đầu ra

5