GESP 题解库 / 5 级题解 / [GESP202603 五级] 有限不循环小数 · 第 2 / 23 题
GESP202603 五级 · P15798 · 简单

有限不循环小数

统计 [L, R] 中有多少个数 a 使得 1/a 是有限不循环小数(即 a 只含质因子 2 和 5)。

📊
L, R ≤ 10⁶
数值范围
🔢
int
数值类型
⚡
O(log²R)
时间复杂度
🎯
数论结论 + 枚举
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

若 1/a 可以化为一个有限的、不循环的小数,则称 a 为终止数。求 [L, R] 中终止数的个数。

例:在 [2, 11] 中,终止数有 2、4、5、8、10,共 5 个。

💡
人话翻译:这是一个经典的数论结论题——1/a 是有限小数 ⟺ a 的质因数只有 2 和 5。换句话说,a 必须能写成 2ˣ × 5ʸ 的形式。所以我们要做的就是在 [L, R] 里数出所有这种形式的数。

🔍 关键词提取

质因数分解有限小数判定枚举 2 与 5 的幂数论结论

已知条件

项目说明
输入一行两个整数 L、R
输出[L, R] 中终止数的个数
数据范围1 ≤ L ≤ R ≤ 10⁶
终止数定义1/a 是有限且不循环的小数
等价条件a = 2ˣ × 5ʸ(x, y ≥ 0)

需要解决的问题

02
思维导图
整理解题思路的全貌
🔢 枚举 2ˣ × 5ʸ
🧠 数论结论
1/a 有限小数
⟺ a = 2ˣ × 5ʸ
不含其他质因子
经典结论务必记牢
🔁 双重枚举
x 从 0 开始,2ˣ ≤ R
y 从 0 开始,2ˣ5ʸ ≤ R
R ≤ 10⁶ → x ≤ 19、y ≤ 8
约 180 个候选
✅ 计数
若在 [L, R] 内 → 计数加 1
用 long long 累乘
超过 R 就 break
⚠️ 易错点
忘记 x = 0 或 y = 0 的情况
把 1 漏掉(1 = 2⁰5⁰)
用 int 累乘溢出
以为要真的算小数
03
样例手算推导
样例 [2, 11] 的逐个检查

🧮 样例:逐个判断 2 ~ 11

对每个数做质因数分解,看是否只含 2 和 5。

数字分解只含 2 和 5?是否终止数
22✅是
33❌ 含质因子 3否
42²✅是
55✅是
62 × 3❌否
77❌否
82³✅是
93²❌否
102 × 5✅是
1111❌否
1
验证 1/4 = 0.25

4 = 2²,符合条件

1/4 = 0.25,确实有限 ✅

✅ 终止数

2
验证 1/6 = 0.1666…

6 = 2 × 3,含质因子 3

1/6 = 0.16666…,无限循环 ❌

❌ 不是终止数

共 5 个 ✓

🧮 用"枚举 2ˣ × 5ʸ"的方法求解

与其逐个分解质因数(每个数最坏 O(√a)),不如直接枚举所有 2ˣ × 5ʸ 形式的数——数量极少。

x2ˣy = 0 ~ 8 得到的数(≤ 11 范围内的)
011、5(2⁰5⁰=1、2⁰5¹=5)
122、10
244
388
416超出 11,但仍要枚举(可能配 y=0 时 16 > 11 就不计)
1
枚举顺序

外层 x:从 0 开始,令 p2 = 2^x,只要 p2 ≤ R

内层 y:从 0 开始,令 v = p2 × 5^y,只要 v ≤ R

若 v ≥ L,就计数加 1

双重循环即可

2
候选总数

R ≤ 10⁶ 时,2^x ≤ 10⁶ → x ≤ 19

5^y ≤ 10⁶ → y ≤ 8

最多 20 × 9 = 180 个候选

远少于逐个分解的 10⁶ 次

✅ 效率极高

🔑
别忘了 x = 0 或 y = 0 的情况:2⁰ × 5⁰ = 1,而 1/1 = 1 确实是有限小数 ✅,所以 1 也是终止数。同理 2⁰ × 5¹ = 5、2¹ × 5⁰ = 2 都要算上。如果循环从 x = 1 开始,就会漏掉这些。
04
解法对比
枚举 2ˣ5ʸ vs 逐个分解质因数

⚔️ 解法对比

🟢 枚举 2ˣ × 5ʸ(推荐) 推荐

双重循环枚举所有候选并判断是否落在区间内

  • 时间 O(log²R)
  • R = 10⁶ 时约 180 个候选
  • 代码 10 行
  • 不需要筛法或分解
💡
实现:for (x = 0, p2 = 1; p2 <= R; x++, p2 *= 2) for (y = 0, v = p2; v <= R; y++, v *= 5) if (v >= L) ans++;

🟠 逐个分解质因数

对 [L, R] 中每个数分解质因数,检查是否只含 2 和 5

  • 时间 O((R−L) × √R)
  • R = 10⁶ 时约 10⁹ 次
  • 可能超时
  • 代码也不短
⚠️
为什么不好:区间最长可达 10⁶,每个数试除到 √a(约 1000 次),总共 10⁹ 次运算,很容易超时。而"枚举候选"的思路把工作量降到了几百次。

📈 性能对比

方案运算量(10⁶ 区间)是否可行
枚举 2ˣ5ʸ约 180✅ 极快
逐个分解约 10⁹❌ 可能超时
05
算法流程图
双重循环枚举 2ˣ × 5ʸ
开始读入 L、R;ans = 0x 从 0 开始,p2 = 2ˣ;只要 p2 ≤ Ry 从 0 开始,v = p2 × 5ʸ;只要 v ≤ Rv ≥ L 吗?是 ✓ans 加 1否 ✗不计数y 加 1,v 乘 5,继续内层x 加 1,p2 乘 2,继续外层输出 ans结束v 还 ≤ R → 继续内层
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔢 终止数统计器

输入 L 和 R,程序会列出所有 2ˣ × 5ʸ 形式的数并统计落在区间内的个数。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long L, R;
    scanf("%lld %lld", &L, &R);

    int ans = 0;

    // 枚举所有 2^x × 5^y 形式的数
    for (long long p2 = 1, x = 0; p2 <= R; p2 *= 2, x++) {
        for (long long v = p2, y = 0; v <= R; v *= 5, y++) {
            if (v >= L) ans++;
        }
    }

    printf("%d\n", ans);
    return 0;
}
🔑
循环里用 v *= 5 累乘而不是每次调用 pow:一是避免浮点误差,二是让每轮只做一次乘法。注意内层循环的 v 必须从 p2 开始(也就是 y = 0 的情形),否则会漏掉"只含 2 的幂"的那些数(如 4、8)。

📖 关键几行怎么看

代码作用为什么这样写
for (p2 = 1; p2 <= R; p2 *= 2)枚举 2 的幂p2 从 1 开始,覆盖 x = 0
for (v = p2; v <= R; v *= 5)枚举 5 的幂从 p2 开始,覆盖 y = 0
if (v >= L) ans++;区间判断等价于 L ≤ v ≤ R
long long类型累乘过程中可能短暂超过 int
⚠️
三个坑:① 内层从 p2 * 5 开始(漏掉 y = 0 的情况);② 外层从 p2 = 2 开始(漏掉 1 这个终止数);③ 用逐个分解质因数的方法,复杂度太高可能超时。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
2 115题面样例
1 111 = 2⁰ × 5⁰,1/1 = 1 是有限小数
1 1071、2、4、5、8、10(还有 1 本身)共 7 个
3 303 含质因子 3
1000 100011000 = 2³ × 5³,是终止数
1 1000000运行验证最大范围
✅
自查清单:① x 从 0 开始吗?② 内层 v 从 p2 开始吗?③ 判断了 v ≥ L 吗?

🚨 易错点清单

⚠️
漏掉 x = 0 或 y = 0:1 = 2⁰5⁰、2 = 2¹5⁰、5 = 2⁰5¹ 都是终止数,循环必须从 1 开始。
⚠️
用逐个分解质因数:区间长达 10⁶ 时会超时,应改用"枚举 2ˣ5ʸ 候选"。
⚠️
忘记判断下界:枚举出的值必须 ≥ L 才计数。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(log₂R × log₅R)
空间复杂度
O(1)
R 最大
10⁶
候选总数
约 180

时间怎么算的?

空间都用在哪?

只用几个变量,不需要额外空间。

✅ 不到 200 次循环,瞬间完成。关键在于"转换视角":不枚举区间里的数,而是枚举可行解。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 数论结论:1/a 是有限小数 ⟺ a 只含质因子 2 和 5
// 证明思路:
//   十进制小数的第 k 位对应分母 10^k = 2^k * 5^k
//   若 a 含其他质因子 p,则 p 无法被 10^k 消掉 -> 必然循环
//   反之若 a = 2^x * 5^y,取 k = max(x, y),则 10^k / a 是整数 -> 有限

// 枚举所有 2^x * 5^y <= R
for (long long p2 = 1; p2 <= R; p2 *= 2)
    for (long long v = p2; v <= R; v *= 5)
        /* 处理 v */;

// 类似思路:枚举"特殊结构的数"而非枚举区间
// 例如"只含因子 3 的数""只含 2、3、5 的数"(丑数)等

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
数论结论有限小数 ⟺ 只含 2、5小数性质、分数化简类题目
枚举可行解不枚举区间而是枚举候选所有"满足特殊条件"的计数题
累乘代替 pow避免浮点误差所有需要幂次的整数运算
🌟
思考题:本题把"质因子只有 2 和 5"换成"质因子只有 2、3、5"(这就是著名的丑数),代码要怎么改?(提示:多加一层循环枚举 3 的幂即可,三重循环最多约 20 × 13 × 9 ≈ 2300 个候选,依然极快。所以"枚举可行解"的思路有很强的可扩展性。)