网硕互联帮助中心题源：洛谷 P15798 [GESP202603 五级] 有限不循环小数
小时候学分数的时候，老师告诉我们
1
2
=
0.5
\\frac{1}{2} = 0.5
21=0.5 是有限小数，
1
3
=
0.333
…
\\frac{1}{3} = 0.333\\ldots
31=0.333… 是无限循环小数。但你有没有想过：为什么偏偏是
2
2
2 和
5
5
5 能让小数"停下来"？如果给你一个范围，比如从
2
2
2 到
11
11
11，你能快速数出有多少个"能让
1
a
\\frac{1}{a}
a1 变成有限小数"的
a
a
a 吗？
这道题来自 2026 年 3 月 GESP 五级认证，表面上是一个简单的区间计数题，实际上它考察的是数论中"有限小数判定定理"的工程化应用。本文将带你从十进制的本质出发，理解为什么分母只能含
2
2
2 和
5
5
5，并把这个思想沉淀成一个可以复用的判定模板。
一、问题本质：小数能不能"停"，分母说了算
很多同学拿到这道题，第一反应是"枚举每个数，然后做除法看能不能除尽"。这个思路在数据范围小的时候没问题，但如果
R
R
R 达到
10
12
10^{12}
1012，除法模拟就彻底失效了。所以我们需要回到数学本质，找到不依赖于具体除法运算的判定方法。
关键定理是这样的：一个最简分数
p
q
\\frac{p}{q}
qp 能化为有限小数，当且仅当分母
q
q
q 的质因数分解中只包含
2
2
2 和
5
5
5。
为什么？因为十进制的基数是
10
=
2
×
5
10 = 2 \\times 5
10=2×5。任何有限小数都可以写成
k
10
n
\\frac{k}{10^n}
10nk 的形式（比如
0.125
=
125
1000
=
1
8
0.125 = \\frac{125}{1000} = \\frac{1}{8}
0.125=1000125=81）。当我们把
1
a
\\frac{1}{a}
a1 通分成这种形式时，分母必须能整除某个
10
n
10^n
10n，而
10
n
=
2
n
×
5
n
10^n = 2^n \\times 5^n
10n=2n×5n，所以
a
a
a 只能由
2
2
2 和
5
5
5 组成。
这道题的核心特征可以概括为以下几点：
- 数学定理驱动：不是模拟除法，而是用数论定理直接判定
- 因子剥离法：通过反复除以
2
2
2 和5
5
5，将"合法"质因子全部去除 - 判定即计数：判定函数足够高效时，可以直接遍历区间计数
- 贪心除尽策略：
2
2
2 和5
5
5 互质，除的顺序不影响结果 - 适用范围广：该定理适用于任意分数的最简形式判定
所以这道题的本质是：把"有限小数"这一数论概念，转化为"质因子只含
2
2
2 和
5
5
5"的可判定条件。
二、解题策略：除尽
2
2
2 和
5
5
5，看还剩什么
面对"
a
a
a 的质因子是否只含
2
2
2 和
5
5
5"的判定问题，最自然的思路是因子剥离：
步骤一：除尽所有
2
2
2。用 while (x % 2 == 0) x /= 2; 把
a
a
a 中所有的因子
2
2
2 全部除掉。
步骤二：除尽所有
5
5
5。用 while (x % 5 == 0) x /= 5; 把剩余的因子
5
5
5 全部除掉。
步骤三：检查结果。如果剩下的数是
1
1
1，说明
a
a
a 只由
2
2
2 和
5
5
5 组成；如果剩下大于
1
1
1，说明还有其他质因子（比如
3
3
3、
7
7
7、
11
11
11 等），
1
a
\\frac{1}{a}
a1 必然是无限循环小数。
这个策略的巧妙之处在于：我们不需要知道
a
a
a 的完整质因数分解，只需要确认"除了
2
2
2 和
5
5
5 之外没有其他质因子"。这就像你检查一个袋子里是否只有红球和蓝球——你不需要数清楚每种球各有多少个，只需要把红球和蓝球全部拿出来，看看袋子里还有没有剩下的球。
三、算法模板：因子剥离判定法
3.1 算法到底在干什么？—— 直觉解释
因子剥离法的核心思想可以用一句话概括：把分母中所有"十进制的合法基因"（
2
2
2 和
5
5
5）全部剔除，看看还有没有"非法残留"。它就像一位严格的安检员，只允许携带
2
2
2 号和
5
5
5 号物品通过，其他一律扣下。
在本题中，安检流程变成：
2
2
2 号物品，有就全部取出
5
5
5 号物品，有就全部取出
1
1
1），放行；如果还有东西（剩下
>
1
>1
>1），拒绝
3.2 万能模板 —— 伪代码 + 实战代码
伪代码：
function IsTerminatingNumber(x):
while x 能被 2 整除:
x = x / 2
while x 能被 5 整除:
x = x / 5
return x == 1
实战代码（C++）：
#include <bits/stdc++.h>
using namespace std;
// 检查一个数是否只包含质因子 2 和 5
// 即：1/a 是否能化为有限小数
bool check(int x)
{
// 步骤一：除尽所有因子 2
while (x % 2 == 0)
{
x /= 2;
}
// 步骤二：除尽所有因子 5
while (x % 5 == 0)
{
x /= 5;
}
// 步骤三：如果最终结果为 1，说明 x 只包含质因子 2 和 5
return x == 1;
}
int main()
{
int l, r, ans = 0;
cin >> l >> r;
// 遍历区间 [l, r]，统计终止数个数
for (int i = l; i <= r; i++)
{
if (check(i))
{
ans++;
}
}
cout << ans << endl;
return 0;
}
3.3 例题实现 —— 本题完整代码
上面的代码已经是本题的完整 AC 代码。核心流程可以概括为：
[
L
,
R
]
[L, R]
[L,R]
i
i
i
以样例
L
=
2
,
R
=
11
L=2, R=11
L=2,R=11 为例：
|
2 2 2 |
1 1 1 |
1 1 1 |
1 1 1 |
是 |
|
3 3 3 |
3 3 3 |
3 3 3 |
3 3 3 |
否 |
|
4 4 4 |
1 1 1 |
1 1 1 |
1 1 1 |
是 |
|
5 5 5 |
5 5 5 |
1 1 1 |
1 1 1 |
是 |
|
6 6 6 |
3 3 3 |
3 3 3 |
3 3 3 |
否 |
|
7 7 7 |
7 7 7 |
7 7 7 |
7 7 7 |
否 |
|
8 8 8 |
1 1 1 |
1 1 1 |
1 1 1 |
是 |
|
9 9 9 |
9 9 9 |
9 9 9 |
9 9 9 |
否 |
|
10 10 10 |
5 5 5 |
1 1 1 |
1 1 1 |
是 |
|
11 11 11 |
11 11 11 |
11 11 11 |
11 11 11 |
否 |
终止数有
2
,
4
,
5
,
8
,
10
2, 4, 5, 8, 10
2,4,5,8,10 共
5
5
5 个，与样例输出一致。
3.4 对比实现 —— 完整质因数分解可行吗？
理论上，我们也可以对
a
a
a 做完整的质因数分解，然后检查分解结果中是否只含
2
2
2 和
5
5
5。但因子剥离法有明显优势：
| 时间复杂度 |
O ( log a ) O(\\log a) O(loga)（只除 2 2 2 和 5 5 5） |
O ( a ) O(\\sqrt{a}) O(a)（需要试除到 a \\sqrt{a} a） |
| 代码复杂度 | 极简单（两个 while 循环） | 较复杂（需要试除表或筛法） |
| 适用范围 | 仅判定"是否只含
2 2 2 和 5 5 5" |
需要完整分解时 |
| 常数因子 | 极小 | 较大 |
因此，对于"有限小数判定"这类只需要确认特定质因子的问题，因子剥离法是更优选择。
3.5 变体清单 —— 这类问题的常见变形
| 其他进制下的有限小数 | 比如二进制、八进制 | 将
2 2 2 和 5 5 5 替换为该进制的质因子（如二进制只含 2 2 2） |
| 分数
p q \\frac{p}{q} qp 的判定（ p ≠ 1 p \\neq 1 p=1） |
需要先将分数化为最简形式 | 用
gcd ( p , q ) \\gcd(p, q) gcd(p,q) 约分后，再对 q q q 做因子剥离 |
| 统计
[ 1 , N ] [1, N] [1,N] 中终止数个数 |
范围从
1 1 1 开始 |
直接遍历，或预处理标记 |
| 求第
k k k 个终止数 |
需要按序生成 | 用优先队列生成
2 i × 5 j 2^i \\times 5^j 2i×5j 的序列 |
| 终止数的乘积/和 | 需要对终止数做运算 | 利用
2 i × 5 j 2^i \\times 5^j 2i×5j 的结构性质 |
| 多组询问 | 多次查询不同区间 | 预处理前缀和数组，
O ( 1 ) O(1) O(1) 回答每次询问 |
3.6 什么时候不能用？—— 边界条件和反例
这个模板虽然好用，但也有明确的适用范围：
-
a
=
0
a = 0
a=0 无意义：1
0
\\frac{1}{0}
01 未定义，题目保证L
≥
1
L \\geq 1
L≥1 -
a
=
1
a = 1
a=1 是终止数：1
=
2
0
×
5
0
1 = 2^0 \\times 5^0
1=20×50，1
1
=
1.0
\\frac{1}{1} = 1.0
11=1.0 是有限小数 - 负数处理：如果区间包含负数，需要取绝对值后再判定
- 非最简分数：如果判定的是
p
q
\\frac{p}{q}
qp 而非1
a
\\frac{1}{a}
a1，必须先用gcd
(
p
,
q
)
\\gcd(p, q)
gcd(p,q) 约分，再对分母做因子剥离。例如2
6
\\frac{2}{6}
62 约分后是1
3
\\frac{1}{3}
31，分母含3
3
3，是无限循环小数 - 大数范围：如果
R
−
L
R – L
R−L 很大（如10
12
10^{12}
1012），需要预处理或数学方法优化，不能直接遍历
四、底层逻辑：为什么这个算法是对的？
4.1 十进制的基因密码
有限小数判定定理的深层原因，在于十进制的构造方式。十进制的每一位代表
10
10
10 的幂次：
0.
a
b
c
=
a
10
+
b
100
+
c
1000
=
100
a
+
10
b
+
c
1000
0.abc = \\frac{a}{10} + \\frac{b}{100} + \\frac{c}{1000} = \\frac{100a + 10b + c}{1000}
0.abc=10a+100b+1000c=1000100a+10b+c
所以任何有限小数都可以写成
k
10
n
\\frac{k}{10^n}
10nk 的形式。当我们把
1
a
\\frac{1}{a}
a1 通分成这种形式时：
1
a
=
k
10
n
⇒
a
⋅
k
=
10
n
=
2
n
×
5
n
\\frac{1}{a} = \\frac{k}{10^n} \\Rightarrow a \\cdot k = 10^n = 2^n \\times 5^n
a1=10nk⇒a⋅k=10n=2n×5n
这意味着
a
a
a 必须是
2
n
×
5
n
2^n \\times 5^n
2n×5n 的约数，因此
a
a
a 的质因子只能含
2
2
2 和
5
5
5。
4.2 因子剥离的完备性
为什么"除尽
2
2
2 和
5
5
5 后检查是否为
1
1
1"是完备的？因为：
- 如果
a
a
a 只含2
2
2 和5
5
5：除尽后必然剩下1
1
1 - 如果
a
a
a 含有其他质因子：比如3
3
3，由于3
3
3 与2
2
2 和5
5
5 都互质，除2
2
2 和5
5
5 的过程中3
3
3 不会被除掉，最终剩余大于1
1
1 - 不存在遗漏：任何正整数的质因数分解是唯一的（算术基本定理），所以不存在"偷偷藏了其他质因子但没被发现"的情况
4.3 从定理到代码的转化
这道题最精彩的地方，不是定理本身，而是如何把抽象的数论定理转化为简洁的代码。完整的质因数分解需要试除法或筛法，但因子剥离法利用了"我们只需要确认没有非法质因子"这一观察，把复杂度从
O
(
a
)
O(\\sqrt{a})
O(a
) 降到了
O
(
log
a
)
O(\\log a)
O(loga)。这提醒我们：在竞赛中，"完整信息"往往不是必须的，"足够做判定"的信息往往可以用更简单的方式获取。
五、决策表：遇到这类问题怎么选算法？
| 判定单个数是否为终止数 | 因子剥离法（两个 while） |
O ( log a ) O(\\log a) O(loga)，代码极简 |
| 需要完整质因数分解 | 试除法 / 线性筛 | 需要所有质因子及其次数 |
| 范围极大（
R ≥ 10 12 R \\geq 10^{12} R≥1012）且多组询问 |
预处理 + 前缀和 / 数学公式 | 避免重复遍历 |
| 分数
p q \\frac{p}{q} qp 的判定 |
先
gcd \\gcd gcd 约分，再因子剥离 |
必须化为最简形式 |
| 其他进制（如二进制） | 替换为对应进制的质因子 | 二进制只含
2 2 2，八进制只含 2 2 2 |
| 求第
k k k 个终止数 |
优先队列生成
2 i × 5 j 2^i \\times 5^j 2i×5j |
按序生成，避免遍历 |
六、工程视角：这个思想在实际中有什么用？
这道题虽然是 GESP 五级的基础题，但其核心思想在工程中有广泛应用：
浮点数精度控制：在计算机中，浮点数的表示基于二进制（
2
2
2 的幂次）。一个十进制有限小数在二进制下可能是无限循环的（比如
0.1
10
=
0.0001100110011
…
2
0.1_{10} = 0.0001100110011\\ldots_2
0.110=0.0001100110011…2），这会导致精度误差。理解"有限小数的质因子判定"有助于程序员预判哪些十进制小数在计算机中会被精确表示，哪些会丢失精度。
金融系统中的金额计算：银行系统中经常需要处理"精确到分"的金额。由于分母通常只涉及
2
2
2 和
5
5
5（如
0.25
0.25
0.25 元、
0.5
0.5
0.5 元、
0.125
0.125
0.125 元等），这些金额在十进制下都是有限小数，可以用整数分（
1
1
1 元
=
100
= 100
=100 分）精确表示。理解这一性质有助于设计不会丢失精分的金融计算系统。
采样率与数字信号处理：在音频/视频处理中，采样率经常设计为
2
2
2 或
5
5
5 的幂次的组合（如
44100
=
2
2
×
3
2
×
5
2
×
7
2
44100 = 2^2 \\times 3^2 \\times 5^2 \\times 7^2
44100=22×32×52×72，但
48000
=
2
7
×
3
×
5
3
48000 = 2^7 \\times 3 \\times 5^3
48000=27×3×53）。理解有限小数的质因子结构，有助于工程师设计不会在时间轴上产生累积误差的采样系统。
七、小结
这道题教会我们的核心认知可以概括为一句话：
一个分数能否化为有限小数，完全由分母的质因子决定——如果分母只含
2
2
2 和
5
5
5，它就是有限小数；否则，它就是无限循环小数。
用公式化语言总结：
1
a
是有限小数
⟺
a
=
2
x
×
5
y
(
x
,
y
≥
0
)
\\frac{1}{a} \\text{ 是有限小数} \\iff a = 2^x \\times 5^y \\quad (x, y \\geq 0)
a1 是有限小数⟺a=2x×5y(x,y≥0)
判定方法：
check
(
a
)
=
(
a
2
v
2
(
a
)
⋅
5
v
5
(
a
)
=
1
)
\\text{check}(a) = \\left( \\frac{a}{2^{v_2(a)} \\cdot 5^{v_5(a)}} = 1 \\right)
check(a)=(2v2(a)⋅5v5(a)a=1)
其中
v
p
(
a
)
v_p(a)
vp(a) 表示质因子
p
p
p 在
a
a
a 中的次数。
这道题的价值不仅在于它本身，更在于它揭示了一类问题的通用解法：当问题涉及"某种数学性质的判定"时，首先尝试寻找判定定理，然后思考如何将定理转化为高效的代码实现——往往不需要完整的信息，只需要"足够做判定"的信息即可。在竞赛中，这种"定理驱动"的思维方式，是区分"暴力选手"和"数学选手"的关键分水岭。
评论前必须登录！
注册