13037.有限不循环小数

markdown
复制
1# 有限不循环小数 题解
2
3## 题目分析
4
5我们需要求出在区间 $[L, R]$ 中“终止数”的个数。终止数的定义为：若 $\frac{1}{a}$ 能化为一个有限且不循环的小数，则 $a$ 为终止数。
6
7这类问题本质上是在考察十进制有限小数的条件：一个最简分数 $\frac{p}{q}$ 能化为有限小数，当且仅当分母 $q$ 的质因子只有 $2$ 和 $5$。题目中的分子是 $1$，分数 $\frac{1}{a}$ 本身已经是最简分数（除非 $a=1$，但 $a \ge 1$），因此 $\frac{1}{a}$ 是有限小数的充要条件就是：$a$ 的质因子只包含 $2$ 和 $5$。
8
9因此，问题转化为：统计 $[L, R]$ 中有多少个整数，其质因数分解中仅含有 $2$ 和 $5$。
10
11## 解题思路
12
13我们可以遍历区间 $[L, R]$ 中的每一个整数 $i$，判断它是否满足条件。判断方法如下：
14
15- 不断将 $i$ 除以 $2$，直到不能整除为止；
16- 再不断将结果除以 $5$，直到不能整除为止；
17- 如果最后剩下的数是 $1$，说明 $i$ 的所有质因子只有 $2$ 和 $5$，那么 $i$ 就是终止数；否则不是。
18
19这种方法不需要提前生成所有终止数，简洁且容易实现。
20
21## 算法说明
22
23设当前要判断的数为 $t = i$。  
241. 当 $t \bmod 2 = 0$ 时，执行 $t \gets t / 2$。  
252. 当 $t \bmod 5 = 0$ 时，执行 $t \gets t / 5$。  
263. 最后若 $t = 1$，则累加答案。
27
28需要注意，当 $i = 1$ 时，$\frac{1}{1}=1$ 是有限小数，但题目数据范围 $L \ge 1$，如果 $L=1$ 需要判断。不过 $1$ 经过除去 $2$ 和 $5$ 后仍为 $1$，会被正确计数。样例中 $L=2$ 没有包含 $1$，需注意题意，但我们的判断逻辑对其同样适用。
29
30## 时间复杂度分析
31
32区间长度最大为 $10^6$。对于每个数 $i$，去除因子 $2$ 和 $5$ 的操作次数是 $O(\log_2 i + \log_5 i)$，这是一个很小的常数。总时间复杂度约为 $O(N \log N)$，其中 $N \le 10^6$，实际运行非常快，可以轻松满足 $1000\text{ms}$ 的时间限制。
33
34空间复杂度为 $O(1)$，仅使用了常数级的额外空间。
35
36## 代码实现
37
38参考代码如下（C++）：
39
40```cpp
41#include <iostream>
42using namespace std;
43
44int main() {
45    int l, r, ans = 0;
46    cin >> l >> r;
47    
48    for (int i = l; i <= r; i++) {
49        int t = i;
50        // 除去所有因子2
51        while (t % 2 == 0)
52            t /= 2;
53        // 除去所有因子5
54        while (t % 5 == 0)
55            t /= 5;
56        // 如果剩下的数是1，则说明仅有2和5因子
57        if (t == 1)
58            ans++;
59    }
60    
61    cout << ans;
62    return 0;
63}

代码解释

1. 读入区间左右端点 l 和 r，并初始化计数器 ans = 0。
2. 用 for 循环遍历 l 到 r 之间的每个整数 i。
3. 对每个 i，用变量 t 保存其值，并不断除以 2，直到不能整除为止；再不断除以 5，直到不能整除为止。
4. 检查最终的 t 是否等于 1。如果是，说明 i 的质因数仅包含 2 和 5，将其计入答案。
5. 循环结束后输出 ans。

总结

本题的核心是理解有限小数与分母质因数的关系，通过简单循环和除法即可高效完成判断。对于 $10^6$ 的数据规模，暴力枚举也是可行的，关键是正确实现因子的去除过程。此类思想在处理“纯因子”相关问题时非常常见，值得掌握。