C++での階乗ゼロ関数のプリイメージサイズ

関数f（x）があるとすると、これはxの階乗の終わりにあるゼロの数を返します。したがって、f（3）=0の場合、3！ =6の最後にはゼロがありませんが、f（11）=2であるため、11！ =39916800の最後に2つのゼロがあります。ここで、Kがある場合、f（x）=Kというプロパティを持つ非負の整数xがいくつあるかを見つける必要があります。

したがって、入力がK =2のような場合、答えは5になります。

これを解決するには、次の手順に従います-

• 関数ok（）を定義します。これにはxが必要です。
• ret：=0
• i：=5を初期化する場合、i <=xの場合、i：=i * 5を更新し、-
  を実行します。
  • ret：=ret + x / i
• return ret
• メインの方法から、次の手順を実行します-
• Kが0と同じ場合、-
  • 5を返す
• 低：=1、高：=K * 5
• 低い<高い間、-
  を実行します
  • 中：=低+（高-低）/ 2
  • x：=ok（mid）
  • 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