資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中階乘零函式的原像大小
假設我們有一個函式f(x)，它將返回x的階乘末尾零的個數。因此，對於f(3) = 0，因為3! = 6末尾沒有零，而f(11) = 2，因為11! = 39916800末尾有兩個零。現在，當我們有K時，我們必須找到有多少個非負整數x具有f(x) = K的屬性。
因此，如果輸入像K = 2，則答案將是5。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式ok()，它將接收x作為引數，
- ret := 0
- for i := 5 to x step i := i * 5 do −
- ret := ret + x / i
- return ret
- 在主方法中，執行以下操作：
- 如果K等於0，則：
- return 5
- low := 1, high := K * 5
- while low < high do −
- mid := low + (high - low) / 2
- x := ok(mid)
- if x < K then −
- low := mid + 1
- 否則
- high := mid
- return (如果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
更新於：2020年6月2日
154 次瀏覽
廣告