统计 [L, R] 中有多少个数 a 使得 1/a 是有限不循环小数(即 a 只含质因子 2 和 5)。
若 1/a 可以化为一个有限的、不循环的小数,则称 a 为终止数。求 [L, R] 中终止数的个数。
例:在 [2, 11] 中,终止数有 2、4、5、8、10,共 5 个。
2ˣ × 5ʸ 的形式。所以我们要做的就是在 [L, R] 里数出所有这种形式的数。质因数分解有限小数判定枚举 2 与 5 的幂数论结论
| 项目 | 说明 |
|---|---|
| 输入 | 一行两个整数 L、R |
| 输出 | [L, R] 中终止数的个数 |
| 数据范围 | 1 ≤ L ≤ R ≤ 10⁶ |
| 终止数定义 | 1/a 是有限且不循环的小数 |
| 等价条件 | a = 2ˣ × 5ʸ(x, y ≥ 0) |
long long 累乘防止溢出,超过 R 就提前退出对每个数做质因数分解,看是否只含 2 和 5。
| 数字 | 分解 | 只含 2 和 5? | 是否终止数 |
|---|---|---|---|
| 2 | 2 | ✅ | 是 |
| 3 | 3 | ❌ 含质因子 3 | 否 |
| 4 | 2² | ✅ | 是 |
| 5 | 5 | ✅ | 是 |
| 6 | 2 × 3 | ❌ | 否 |
| 7 | 7 | ❌ | 否 |
| 8 | 2³ | ✅ | 是 |
| 9 | 3² | ❌ | 否 |
| 10 | 2 × 5 | ✅ | 是 |
| 11 | 11 | ❌ | 否 |
4 = 2²,符合条件
1/4 = 0.25,确实有限 ✅
✅ 终止数
6 = 2 × 3,含质因子 3
1/6 = 0.16666…,无限循环 ❌
❌ 不是终止数
共 5 个 ✓
与其逐个分解质因数(每个数最坏 O(√a)),不如直接枚举所有 2ˣ × 5ʸ 形式的数——数量极少。
| x | 2ˣ | y = 0 ~ 8 得到的数(≤ 11 范围内的) |
|---|---|---|
| 0 | 1 | 1、5(2⁰5⁰=1、2⁰5¹=5) |
| 1 | 2 | 2、10 |
| 2 | 4 | 4 |
| 3 | 8 | 8 |
| 4 | 16 | 超出 11,但仍要枚举(可能配 y=0 时 16 > 11 就不计) |
外层 x:从 0 开始,令 p2 = 2^x,只要 p2 ≤ R
内层 y:从 0 开始,令 v = p2 × 5^y,只要 v ≤ R
若 v ≥ L,就计数加 1
双重循环即可
R ≤ 10⁶ 时,2^x ≤ 10⁶ → x ≤ 19
5^y ≤ 10⁶ → y ≤ 8
最多 20 × 9 = 180 个候选
远少于逐个分解的 10⁶ 次
✅ 效率极高
2⁰ × 5⁰ = 1,而 1/1 = 1 确实是有限小数 ✅,所以 1 也是终止数。同理 2⁰ × 5¹ = 5、2¹ × 5⁰ = 2 都要算上。如果循环从 x = 1 开始,就会漏掉这些。双重循环枚举所有候选并判断是否落在区间内
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
| 方案 | 运算量(10⁶ 区间) | 是否可行 |
|---|---|---|
| 枚举 2ˣ5ʸ | 约 180 | ✅ 极快 |
| 逐个分解 | 约 10⁹ | ❌ 可能超时 |
输入 L 和 R,程序会列出所有 2ˣ × 5ʸ 形式的数并统计落在区间内的个数。
点按钮开始 →
#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 这个终止数);③ 用逐个分解质因数的方法,复杂度太高可能超时。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
2 11 | 5 | 题面样例 |
1 1 | 1 | 1 = 2⁰ × 5⁰,1/1 = 1 是有限小数 |
1 10 | 7 | 1、2、4、5、8、10(还有 1 本身)共 7 个 |
3 3 | 0 | 3 含质因子 3 |
1000 1000 | 1 | 1000 = 2³ × 5³,是终止数 |
1 1000000 | 运行验证 | 最大范围 |
只用几个变量,不需要额外空间。
✅ 不到 200 次循环,瞬间完成。关键在于"转换视角":不枚举区间里的数,而是枚举可行解。
// 数论结论: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 | 避免浮点误差 | 所有需要幂次的整数运算 |