数据结构
网络
关系数据库管理系统 (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 次浏览
广告