C ++中阶乘零函数的原像大小

假设我们有一个函数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，当i <= x时，更新i：= i * 5，做-

• ret：= ret + x / i

• 返回ret

• 从主要方法中，执行以下操作-

• 如果K等于0，则-

• 返回5

• 低：= 1，高：= K * 5

• 当低<高时，执行-

• 高：=中

• 低：=中+ 1

• 中：=低+（高-低）/ 2

• x：= ok（中）

• 如果x <K，则-

• 除此以外

• 返回（如果ok(low)与K相同，则为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;
   }
};
main(){
   Solution ob;
   cout << (ob.preimageSizeFZF(2));
}

输入值

2

输出结果

5