问题描述
满足 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 的贡献是分层的:
-
第一层贡献:能被 55 整除的数(如 5,10,15,…5,10,15,…),每个贡献 1 个 55。
-
第二层贡献:能被 2525 整除的数(如 25,50,75,…25,50,75,…),每个额外贡献 1 个 55(已计入第一层,此处是第二个 55)。
-
第三层贡献:能被 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;
//}