P4697 符合条件的自然数加强版（【提高】）

解题思路

n! 末尾 0 的个数，等于 1 到 n 中因子 5 的个数。因为每个末尾的 0 需要一对因子 2 和 5，而因子 2 的数量永远比 5 多，所以只看 5 就够了：zeros(n) = n/5 + n/25 + n/125 + ……。下面分三步实现。

**第一步，写 zeros 函数。**用循环累加统计 1 到 n 里因子 5 的个数：while (n) { n /= 5; count += n; }。比如 zeros(25) = 25/5 + 25/25 = 5 + 1 = 6，表示 25! 末尾有 6 个 0。

**第二步，二分查找。**zeros 函数随 n 增大而单调不降（n 越大，因子 5 越多），所以可以二分。在 [1, targetZeros×5+10] 范围内二分找最小的 n 满足 zeros(n) ≥ targetZeros：如果 zeros(mid) ≥ targetZeros，答案在左半部分，high = mid；否则答案在右半部分，low = mid + 1。

**第三步，验证答案。**二分结束后 low 是最小的满足 zeros(low) ≥ targetZeros 的数。检查 zeros(low) 是否恰好等于 targetZeros：等于就输出 low；不等于说明 targetZeros 个 0 不可能恰好出现（会"跳过去"），输出 No solution。

注意边界情况：targetZeros=0 时答案是 1，因为 1! = 1 末尾有 0 个 0，二分也能正确找到它。targetZeros 最大到 1e8，n 会接近 4 亿，必须用 long long 存，防止溢出。

为什么可以二分？zeros 函数单调不减——n 越大，末尾 0 只增不减，所以存在一个分界点，二分能快速找到它，这比从 1 一个一个试要快得多。

参考代码

// P4697 符合条件的自然数加强版：求最小的自然数n，使n!末尾恰好有x个连续的0
#include <iostream>
using namespace std;

// 计算n!末尾有多少个0（1到n中因子5的个数）
long long zeros(long long n) {
    long long count = 0;
    while (n) {
        n /= 5;
        count += n;
    }
    return count;
}

int main() {
    long long targetZeros;
    cin >> targetZeros;
    // 二分找最小的n，使得zeros(n) >= targetZeros
    long long low = 1, high = targetZeros * 5 + 10;
    while (low < high) {
        long long mid = (low + high) / 2;
        if (zeros(mid) >= targetZeros) high = mid;
        else low = mid + 1;
    }
    if (zeros(low) == targetZeros) cout << low << endl;
    else cout << "No solution" << endl;
    return 0;
}

复杂度分析

二分范围大约是 O(x)，每次判断 zeros 需要 O(log n) 次除法，所以总时间复杂度 O(log x · log x)。x 最大 1e8，只需要几十次运算，非常快。空间 O(1)。