C++实现有限不循环小数判断算法解析

1. 题目背景与核心概念解析

这道GESP五级真题"有限不循环小数"考察的是C++编程中对分数与小数转换关系的理解。我们先明确几个关键概念：

有限不循环小数是指小数部分位数有限且不循环的有理数，例如0.5、0.125等。从数学角度看，这类小数可以表示为分母只包含质因数2和5的分数。例如：

• 0.5 = 1/2
• 0.125 = 1/8 = 1/(2³)
• 0.04 = 1/25 = 1/(5²)

1.1 数学原理与算法思路

判断一个分数是否为有限不循环小数的核心算法是：

1. 将分数化简为最简形式a/b
2. 对分母b进行质因数分解
3. 检查分母b的质因数是否只包含2和5

在C++实现中，我们需要解决以下技术难点：

• 最大公约数(GCD)计算
• 分母的质因数分解
• 质因数检查逻辑

1.2 输入输出规格分析

根据洛谷P15798题目描述，输入格式通常为：

code复制T
a1 b1
a2 b2
...
aT bT

其中T是测试用例数量，每组数据包含分子a和分母b。输出应对每个测试用例判断a/b是否为有限不循环小数，输出"Yes"或"No"。

2. 核心算法实现

2.1 最大公约数计算

使用欧几里得算法计算GCD，这是化简分数的第一步：

cpp复制int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

2.2 分数化简与分母处理

化简分数并获取处理后的分母：

cpp复制void simplify(int &a, int &b) {
    int g = gcd(a, b);
    a /= g;
    b /= g;
}

2.3 质因数检查

关键函数：检查分母是否只含2和5的质因数

cpp复制bool isFiniteDecimal(int b) {
    if (b == 1) return true;  // 分母为1时是整数
    
    // 去除所有因子2
    while (b % 2 == 0) b /= 2;
    
    // 去除所有因子5
    while (b % 5 == 0) b /= 5;
    
    retur