蓝桥备战 每日一题 （1）

二分法

代码如下：

#include<iostream>
#define ll long long
using namespace std;

ll query(ll n)
{
	ll ret = 0;
	while (n > 0) {
		ret += n / 5;   // 要计算 从 1 到 n 中 是 5 的倍数的个数，但是要注意 如果是 25 ，要计算两次
		n /= 5;
	}
	return ret;
}

int main()
{
	ll k;
	cin >> k;
	ll s = 1, r = 0x7fffffffffffffff;
	while (s < r)
	{
		ll mid = s + (r - s >> 1);
		if (query(mid) < k) 
			s = mid + 1;
		else r = mid;
	}
	if (query(s) == k) cout << s;
	else cout << -1;
	return 0;
}

这个代码比较难以懂的就是 query 函数那里求解 从 1 到 n 中是 5 的倍数的累加，这里不是单纯的累加，如果一个数 是 25 ，那么这个数 对 5 的累加可以贡献两次，因为
$$5^2=25$$

5 的上标是 2 ，所以会有两次贡献，然后就使用二分的方法来完成就行，还有 处理 mid 的时候，没有使用 ( s + r ) / 2, 这是因为如果 s 和 r 很大的话，相加起来可能会超过 long long的范围。