本文涉及的基础知识点
题目
f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 * 2 * 3 * … * x，且 0! = 1 。
例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。
给定 k，找出返回能满足 f(x) = k 的非负整数 x 的数量。
示例 1：
输入：k = 0
输出：5
解释：0!, 1!, 2!, 3!, 和 4! 均符合 k = 0 的条件。
示例 2：
输入：k = 5
输出：0
解释：没有匹配到这样的 x!，符合 k = 5 的条件。
示例 3:
输入: k = 3
输出: 5
参数范围
0 <= k <= 109
分析
时间复杂度
O(logn*log5n)。FirstEqualMore内的循环logn次，GetNum内循环log5N。
0个数
0的个数就是2和5的个数的较小者。5的个数一定不会多余2的个数，所以计算5的个数就可以了。
如果5x<=value，那么2x一定小于value。
除非是0个，否则5的个数一定不会等于2的个数。
令x>0，则5x/2 = 2x+x/2 >2x > x
5个数
初步想法
| 非25的倍数，5的倍数 | +1 |
| 非125的倍数，25的倍数 | +2 |
| 非625的倍数，125的倍数 | +3 |
| … |
可以这样想
| 5的倍数 | +1 |
| 25的倍数 | +1 |
| 125的倍数 | +1 |
| … |
二分
初：寻找第一个和最后一个x，使得f(x)等于k，两者相减再+1。要特殊处理不存在f(x)等于k。所以改成寻找x1=第一个f(x)大于等于k，x2=第一个f(x)大于k，x2也是第一个f(x)大于等于k+1。
代码
核心代码
class Solution { public: int preimageSizeFZF(int k) { return FirstEqualMore(k + 1) - FirstEqualMore(k); } int FirstEqualMore(int k) { long long left = -1, right = k * 5LL; while (right - left > 1) { const auto mid = left + (right - left) / 2; if (GetNum(mid) >= k) { right = mid; } else { left = mid; } } return right; } long long GetNum(long long llVaue) { long long llRet = 0; long long five = 5; while (five <= llVaue) { llRet += llVaue / five; five *= 5; } return llRet; } };
测试用例
template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<vector> grid; int res = 0; { Solution slu; res = slu.preimageSizeFZF(0); Assert(5, res); } { Solution slu; res = slu.preimageSizeFZF(5); Assert(0, res); } { Solution slu; res = slu.preimageSizeFZF(3); Assert(5, res); }
//CConsole::Out(res);
}
2023年3月旧代码
如果f(x)等于k，则f(x+1)、f(x+2)、f(x+3)、f(x+4)都等于k。如果不存在f(x)等于k，则结果为0。所以只有两种返回值，5或0。
class Solution { public: int preimageSizeFZF(int k) { int left = 0, right = 1000 * 1000 * 1000 + 1; while (right > left + 1) { int iMid = left + (right - left) / 2; const int iNum = GetFiveNum(iMid); if (iNum == k) { return 5; } else if (iNum < k) { left = iMid; } else { right = iMid; } } return (GetFiveNum(left) == k) ? 5 : 0; } //获取[0,iMax*5] 质因数5的个数 int GetFiveNum(int iMax) { int iNum = iMax; int tmp = 5; while (iMax >= tmp) { iNum += iMax / tmp; tmp *= 5; } return iNum; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 洒家想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
