「EGOI2021」零的个数 题解

题目分析

我们需要找到区间 $[a, b]$ 内所有整数的最小公倍数 $L = \text{lcm}(a, a+1, \ldots, b)$，然后计算 $L$ 末尾有多少个零。

关键观察：一个数末尾零的个数等于其质因数分解中 $2$ 和 $5$ 的指数的最小值。

数学推导

1. 末尾零的本质

设 $L = 2^\alpha \cdot 5^\beta \cdot M$，其中 $M$ 不被 $2$ 或 $5$ 整除，那么末尾零的个数为 $\min(\alpha, \beta)$。

2. 最小公倍数的质因数分解

对于质数 $p$，在 $\text{lcm}(a, a+1, \ldots, b)$ 中 $p$ 的指数等于区间 $[a, b]$ 中 $p$ 的最高幂次。

即：

$$\text{exp}_p(L) = \max\{k : \exists x \in [a, b] \text{ 使得 } p^k \mid x\} $$

3. 问题转化

我们需要计算：

• $\alpha = \max\{k : \exists x \in [a, b] \text{ 使得 } 2^k \mid x\}$
• $\beta = \max\{k : \exists x \in [a, b] \text{ 使得 } 5^k \mid x\}$

答案就是 $\min(\alpha, \beta)$。

算法思路

方法一：直接枚举（适用于小数据）

对于 $b \leq 40$ 的情况，可以实际计算 LCM：

#include <iostream>
#include <algorithm>
using namespace std;

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b;
}

int countZeros(long long n) {
    int cnt = 0;
    while (n % 10 == 0) {
        cnt++;
        n /= 10;
    }
    return cnt;
}

int main() {
    long long a, b;
    cin >> a >> b;
    
    long long L = a;
    for (long long i = a + 1; i <= b; i++) {
        L = lcm(L, i);
    }
    
    cout << countZeros(L) << endl;
    return 0;
}

方法二：数学分析（适用于大数据）

对于 $a, b \leq 10^{18}$，我们需要高效的数学方法：

#include <iostream>
#include <algorithm>
using namespace std;

// 计算在区间[a, b]中，p^k的倍数是否存在
bool exists_power(long long a, long long b, long long p, int k) {
    long long power = 1;
    for (int i = 0; i < k; i++) {
        if (power > b / p) return false; // 防止溢出
        power *= p;
    }
    // 检查区间内是否存在power的倍数
    long long first_multiple = ((a + power - 1) / power) * power;
    return first_multiple <= b;
}

int main() {
    long long a, b;
    cin >> a >> b;
    
    // 计算2的最高幂次
    int max_power_2 = 0;
    for (int k = 1; ; k++) {
        if (!exists_power(a, b, 2, k)) {
            max_power_2 = k - 1;
            break;
        }
    }
    
    // 计算5的最高幂次
    int max_power_5 = 0;
    for (int k = 1; ; k++) {
        if (!exists_power(a, b, 5, k)) {
            max_power_5 = k - 1;
            break;
        }
    }
    
    cout << min(max_power_2, max_power_5) << endl;
    return 0;
}

优化版本

由于 $2^k$ 和 $5^k$ 增长很快，循环次数不会太多：

#include <iostream>
#include <algorithm>
using namespace std;

int count_trailing_zeros(long long a, long long b) {
    int count_2 = 0, count_5 = 0;
    
    // 统计因子2的最高幂次
    long long power_2 = 1;
    for (int k = 1; ; k++) {
        if (power_2 > b / 2) break; // 防止溢出
        
        power_2 *= 2;
        // 检查区间内是否存在power_2的倍数
        long long first = ((a + power_2 - 1) / power_2) * power_2;
        if (first <= b) {
            count_2 = k;
        } else {
            break;
        }
    }
    
    // 统计因子5的最高幂次
    long long power_5 = 1;
    for (int k = 1; ; k++) {
        if (power_5 > b / 5) break; // 防止溢出
        
        power_5 *= 5;
        // 检查区间内是否存在power_5的倍数
        long long first = ((a + power_5 - 1) / power_5) * power_5;
        if (first <= b) {
            count_5 = k;
        } else {
            break;
        }
    }
    
    return min(count_2, count_5);
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << count_trailing_zeros(a, b) << endl;
    return 0;
}

样例分析

样例1：1 6

• 检查 $2^k$：$2^1=2$ (存在), $2^2=4$ (存在), $2^3=8$ (不存在) → count_2 = 2
• 检查 $5^k$：$5^1=5$ (存在), $5^2=25$ (不存在) → count_5 = 1
• 答案：min(2, 1) = 1

样例2：10 11

• 检查 $2^k$：$2^1=2$ (存在), $2^2=4$ (存在), $2^3=8$ (存在), $2^4=16$ (不存在) → count_2 = 3
• 检查 $5^k$：$5^1=5$ (存在), $5^2=25$ (不存在) → count_5 = 1
• 答案：min(3, 1) = 1

算法正确性

1. 完备性：检查了所有可能的 $2^k$ 和 $5^k$
2. 正确性：基于最小公倍数的质因数分解性质
3. 高效性：循环次数为 $O(\log b)$

复杂度分析

• 时间复杂度：$O(\log b)$，因为 $2^k$ 和 $5^k$ 指数增长
• 空间复杂度：$O(1)$
• 支持范围：$a, b \leq 10^{18}$

总结

这道题的关键在于：

1. 理解末尾零与质因子 $2$、$5$ 的关系
2. 掌握最小公倍数的质因数分解性质
3. 使用数学方法避免直接计算大数

通过检查区间内是否存在 $2^k$ 和 $5^k$ 的倍数，我们可以高效地解决问题，即使对于 $10^{18}$ 的大数据范围。