【GESP】C++五级真题 luogu-P15798, [GESP202603 五级] 有限不循环小数

2026年3月，GESP五级真题，考察数论基础（质因数分解特性）枚举算法，难度⭐⭐★☆☆。洛谷难度级别：普及-。

P15798 [GESP202603 五级] 有限不循环小数

题目要求

题目描述

若 $\frac{1}{a}$ 可化为一个有限的，不循环的小数，则称 $a$ 为终止数。 请你求出在 $L$ 到 $R$ 中终止数的数量。

输入格式

输入一行，包含两个整数 $L,R$。

输出格式

输出一行，包含一个整数，表示 $L$ 到 $R$ 中终止数的数量。

输入输出样例 #1

输入 #1

2 11

输出 #1

5

说明/提示

样例解释

在 $[2,11]$ 中，终止数有 $2$、$4$、$5$、$8$、$10$。

数据范围

保证 $1 \le L \le R \le 10^6$。

题目分析

这道题目虽然披着"小数"的外衣，本质上是一道数论题。在 GESP 五级考试中，数论基础（如质数判断、质因数分解、最大公约数等）是高频重点。

数学原理破解：什么样的分数能化成有限且不循环的小数？

我们在小学数学中学过：一个最简分数能不能化成有限小数，完全取决于它的分母 $a$。由于我们使用的数学计数法是十进制（逢十进一），而 $10 = 2 \times 5$。

逻辑推导是这样的：

假设 $\frac{1}{a}$ 可以化为有限小数，这意味着它一定可以写成 $\frac{k}{10^n}$ 的形式（其中 $k$ 和 $n$ 都是正整数）。 由 $\frac{1}{a} = \frac{k}{10^n}$，我们可以通过交叉相乘推导出 $a \times k = 10^n$。 因为 $10^n = (2 \times 5)^n = 2^n \times 5^n$，即 $10^n$ 这个数字的全部质因数只有 $2$ 和 $5$。 既然 $a$ 是 $10^n$ 的一个约数（因为 $a$ 乘以整数 $k$ 等于 $10^n$），那么 $a$ 身上包含的质因数必定也只能是 $2$ 或 $5$，绝不可能含有 $3, 7, 11$ 等其它任何质数。

因此，当且仅当一个数 $a$ 的质因数只包含 $2$ 和 $5$ 时，$\frac{1}{a}$ 才能被除尽，化为有限且不循环的小数。 也就是说，所谓"终止数" $a$，一定满足特定的数学构造形式：$a = 2^x \times 5^y$（其中 $x$ 和 $y$ 是非负整数，即 $x \ge 0, y \ge 0$），并且 $a$ 必须在题目要求的范围之内。

算法思路：如何找到所有终止数？

有了上面的数学结论，接下来就是怎么在 $[L, R]$ 的范围内找到所有满足条件的数。这里提供两种思路：

思路一：逐个检验法（直接分解）

最直观的想法：从 $L$ 到 $R$，每个数都拿过来"查户口"。对于当前数 $a$，不停地除以 $2$（只要能整除就除），再不停地除以 $5$（只要能整除就除），把 $2$ 和 $5$ 的因子全部剥干净。如果最后剩下的数等于 $1$，说明 $a$ 的质因数只有 $2$ 和 $5$，它就是"终止数"；否则说明它还含有其他质因数，不合格。

这个方法逻辑简单清晰，容易理解和编写。时间复杂度为 $O((R - L) \times \log R)$，在 $R \le 10^6$ 的数据范围内完全够用。

思路二：主动生成法（枚举幂次）

换一个角度——与其挨个排查，不如直接按照公式把所有终止数"造"出来。

既然终止数的形式是 $a = 2^x \times 5^y$，我们只需要用两层循环枚举 $x$ 和 $y$ 的值：

• $2$ 的幂次 $x$：因为 $2^{20} = 1048576 > 10^6$，所以 $x$ 从 $0$ 枚举到 $19$ 就足够了。
• $5$ 的幂次 $y$：因为 $5^8 = 390625$，$5^9 > 10^6$，所以 $y$ 从 $0$ 枚举到 $8$ 就足够了。

这样总共只有大约 $20 \times 9 = 180$ 次判定，效率极高。最后判断生成的 $a$ 是否落在 $[L, R]$ 内即可。

示例代码

思路一：逐个检验法（直接分解）

#include <iostream>

// 判断一个数是否为"终止数"
// 核心逻辑：不断除以 2 和 5，看最终能否除尽变成 1
bool isTerminating(int a) {
    // 先把所有的因子 2 除干净
    while (a % 2 == 0) {
        a /= 2;
    }
    // 再把所有的因子 5 除干净
    while (a % 5 == 0) {
        a /= 5;
    }
    // 如果剩下的是 1，说明 a 的质因数只有 2 和 5
    return a == 1;
}

int main() {
    int L, R;
    std::cin >> L >> R;

    int ans = 0; // 用于统计符合要求的"终止数"的个数

    // 从 L 到 R，逐个检验每个数是否为终止数
    for (int i = L; i <= R; i++) {
        if (isTerminating(i)) {
            ans++;
        }
    }

    // 输出最终结果
    std::cout << ans << std::endl;

    return 0;
}

思路二：主动生成法（枚举幂次）

#include <iostream>

int main() {
    long long L, R;
    std::cin >> L >> R;

    int ans = 0; // 用于统计符合要求的"终止数"的个数

    // 外层循环枚举 2 的幂次，变量 p2 用来存放 2^x 的值
    // p2 不断乘以 2，直到超出 R 的最大范围
    for (long long p2 = 1; p2 <= R; p2 *= 2) {

        // 内层循环枚举 5 的幂次，变量 p5 用来存放 5^y 的值
        // p5 不断乘以 5，同时我们要确保 p2 * p5 的总积不能超过 R
        for (long long p5 = 1; p2 * p5 <= R; p5 *= 5) {

            // 组装出当前的 a 值
            long long a = p2 * p5;

            // 如果这个生成的 a 值刚好落在 [L, R] 范围内，计数加一
            if (a >= L && a <= R) {
                ans++;
            }
        }
    }

    // 最终输出满足条件的数量
    std::cout << ans << std::endl;

    return 0;
}

代码解析小贴士

1. 思路一的核心技巧——"剥洋葱"： 判断一个数的质因数是否只包含 $2$ 和 $5$，不需要做完整的质因数分解。只要用 while 循环反复除以 $2$、再反复除以 $5$，最后看结果是不是 $1$。如果是 $1$，说明"洋葱"已经被剥光了，质因数确实只有 $2$ 和 $5$。这个技巧在数论题中非常实用。
2. 思路二的效率优势——"查户口"不如"自己生"： 当在一个大范围里寻找具备极少特征的特殊数字时，从头到尾挨个排查虽然可行但比较笨拙。把特殊的数字按照生成规则反向拼装创造出来，往往能将时间复杂度从 $O(N \log N)$ 降到 $O(\log^2 N)$。
3. 乘风破浪的 long long： 在思路二中，尽管题目给定 $R \le 10^6$ 还在 int 承受范围内，但是在写底数倍增循环（如 p2 *= 2, p5 *= 5）时，下一次循环乘后的预判值极容易越界爆出 int 的上限导致死循环或错误。在处理所有涉及连乘倍增的题目时，养成使用 long long 的好习惯。