欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 社会 > 蓝桥杯备赛-二分-求阶乘

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

2025/3/17 1:49:04 来源:https://blog.csdn.net/m0_74797130/article/details/146262703  浏览:    关键词:蓝桥杯备赛-二分-求阶乘

问题描述

满足 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;
//}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词