蓝桥杯备赛-二分-求阶乘

问题描述

满足 NN ! 的末尾恰好有 KK 个 0 的最小的 NN 是多少?

如果这样的 NN 不存在输出 −1−1 。

输入格式

一个整数 KK 。

输出格式

一个整数代表答案。

样例输入

2

样例输出

10

评测用例规模与约定

对于 30%30% 的数据, 1≤K≤1061≤K≤106.

对于 100%100% 的数据, 1≤K≤10181≤K≤1018.

如何计算 5 的因子数？

每个数对 55 的贡献是分层的：

1. 第一层贡献：能被 55 整除的数（如 5,10,15,…5,10,15,…），每个贡献 1 个 55。

2. 第二层贡献：能被 2525 整除的数（如 25,50,75,…25,50,75,…），每个额外贡献 1 个 55（已计入第一层，此处是第二个 55）。

3. 第三层贡献：能被 125125 整除的数（如 125,250,…125,250,…），每个再额外贡献 1 个 55，以此类推。

• 逐层统计：通过不断除以 5，依次统计每一层（5,10,125,……）的贡献。

#include<iostream>
#include<climits>
using namespace std;
//阶乘末尾的零由因子2和5的对数决定，而由于2的数量远多于5，因此零的数量由5的因子数量决定。
long long check(long long n) {long long cnt = 0;while (n){n /= 5;//按5的幂分层计算影响，5,25,125,......cnt += n;}return cnt;
}
//二分，check(middle)>=k,猜大了，r=middle;
int main()
{long long k;cin >> k;long long l = 0;long long r = LLONG_MAX;while (l < r) {long long middle = (l + r) / 2;if (check(middle) >= k) r = middle;else l = middle + 1;}//l=r时停止if (check(l) == k) cout << l;else cout << "-1";return 0;
}
//暴力循环
//int main()
//{
//	long long k;
//	cin >> k;
//	for (long long i = 5; ; i += 5) 
//	{
//		if (check(i) < k) continue;
//		if (check(i) == k) {
//			cout << i;
//			break;//忘记了
//		}
//		if (check(i) == k) {
//			cout << "-1";
//			break;//忘记了
//		}
//	}
//	return 0;
//}