企业官网建设流程全解析

我记得第一次刷到PAT乙级1062这道“最简分数”时，心里多少有点不以为然——求个最大公约数的事，至于单独出一整道题吗？结果真上手一写，连着交了三回都没过，不是答案错就是格式错。后来把这题彻底吃透才发现，它几乎把乙级真题最爱埋的雷全踩了一遍：浮点数比较的精度陷阱、端点是否包含、输入顺序不保证、整数溢出隐患，以及枚举上界不是K-1这种容易一眼看错的细节。如果你正在跟翁恺老师的习题集复习C语言，或者准备PAT乙级考试，这道题值得你稍微停一下。下面我完整拆一下：这题到底考什么、为什么不能无脑用double比大小，以及一份能稳定AC的C语言实现。

1. 题目本身很简单，但三个考点一个比一个阴

1.1 先把题目用大白话还原一遍

输入一行，给两个正分数N1/M1和N2/M2，再给一个正整数分母K。要求你把这个区间内所有分母恰好等于K的最简分数，按从小到大输出，行首尾不能有多余空格。题目保证至少会有一个输出。

样例是这样的：

7/18 13/20 12

输出：

5/12 7/12

7/18约等于0.3889，13/20是0.65，分母为12的分数里，5/12约0.4167、7/12约0.5833，正好都落在区间里，而且5和12、7和12都互质，所以输出这两项。中间还有个6/12也就是1/2，虽然也在区间里，但它不是最简分数，必须扔掉。

这一步看起来没有任何难度，但“最简分数”这四个字翻译成代码逻辑，就是gcd(分子, 分母) == 1。这一下就把考点拉到了两个基础算法上：最大公约数的求法，以及枚举时怎么判断一个分数是否该输出。

1.2 隐藏的三个核心考点

我刷完这题之后总结了三个真正决定生死的点：

• 分数比较不能用浮点数：后面专门讲，这是最容易让新手翻车的地方。
• 最简分数的判定必须用gcd：写错递归边界或者忘记判断，都会导致多输出或少输出。
• 枚举上界不是K-1：很多人默认分母是K，那分子就是1到K-1，但这个前提是“所有候选分数都小于1”。题目说的是两个正分数，分子完全可以大于分母，候选分子就会超过K-1，甚至超过K。这一点等会儿用一个具体例子说明。

所以这道题本质考的不是“会不会写gcd”，而是对整数运算边界和区间语义的敏感度。乙级里很多题都是这样：看着是基础题，实际埋了一堆边界条件。

2. 为什么不能无脑转double：交叉相乘才是正解

2.1 double在分数比较上的精度极限

新手最自然的想法是：把n1/m1和n2/m2直接转成浮点数，循环里把i/k也转成double，然后比大小不就行了？

在小数据下确实没问题，比如样例这种分母只有十几的数。但PAT的测试点不会让你舒服。double虽然能表示大约15到17位有效十进制数字，可当两个分数非常接近时，它们的差值可能小于浮点数在当前量级下的分辨能力，于是两个明明不相等的分数在double里被判定为相等，直接漏解。

举个例子，1/10000000和2/20000001，这两个分数的差值大约是5e-17，已经在double的有效精度边缘晃了。真正考场上你根本不知道测试点卡在哪，与其赌浮点精度，不如从根上用整数运算。

还有一个更隐蔽的问题：排序时如果依赖double，一旦两个分数被误判为相等，交换逻辑就会出错，进而影响整个枚举区间。

2.2 交叉相乘的数学推导和代码写法

判断a/b和c/d的大小，不需要真的算出小数。因为b和d都是正数，所以：

a/b < c/d 等价于 a*d < c*b

两边同时乘上b*d，不等式方向不变。这就是交叉相乘。

用在这道题里就是：设两个分数分别为n1/m1和n2/m2，且已经保证n1/m1是较小的一方。对于候选分数i/k，需要满足：

n1/m1 < i/k < n2/m2

拆开写就是两个条件：

n1 * k < i * m1 i * m2 < n2 * k

注意这里四个量全用long long，因为n1*k这种乘积如果n1和k都达到10的5次方量级，乘积就是10的10次方，int早就爆了。

2.3 输入顺序不保证，必须先排序

题目只说“两个不相等的正分数”，没说第一个一定小于第二个。很多人写代码时默认n1/m1是左端点，结果第一个测试点可能就过不了。

排序也建议用交叉相乘而不是double：

if (n1 * m2 > n2 * m1) { long long t; t = n1; n1 = n2; n2 = t; t = m1; m1 = m2; m2 = t; }

四个变量一起换，只换分子或者只换分母都会出大问题。

2.4 gcd：欧几里得算法在这里的唯一任务

判断最简分数，就是判断分子分母互质，即最大公约数为1。用辗转相除法：

long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }

递归的终止条件是b为0，此时a就是最大公约数。比如gcd(12, 5)会先变成gcd(5, 2)，再变成gcd(2, 1)，最后gcd(1, 0)返回1。如果gcd(i, k) == 1，说明这个分数不能再约分，可以输出。

3. 枚举上界是个大坑：完整代码与逐行解释

3.1 为什么循环不能只写到K-1

很多参考代码写成：

for (int i = 1; i < k; i++)

这个写法在“两个分数都小于1”的常规样例里能过，但逻辑上是错的。当区间内有分数大于等于1时，分母为K的候选分数，分子可能大于K。

举个例子：输入1/2 3/2 4。区间是0.5到1.5，分母为4的候选分数有3/4（0.75）和5/4（1.25），以及4/4（等于1但不最简，gcd(4,4)=4）。如果循环只跑到i < 4，那5/4就被漏掉了，因为它的分子5大于分母4。

所以正确做法是把循环上界交给条件控制，而不是拍脑袋写一个K。判断候选分数i/k是否还在右端点n2/m2的左边，等价于：

i * m2 < n2 * k

只要这个条件还成立，i就可以继续增大。一旦不成立，说明i/k已经不小于右端点，后面更大，更不可能落在区间内。

3.2 可稳定AC的完整C代码

#include <stdio.h> long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); } int main(void) { long long n1, m1, n2, m2, k; scanf("%lld/%lld %lld/%lld %lld", &n1, &m1, &n2, &m2, &k); // 统一左小右大 if (n1 * m2 > n2 * m1) { long long t; t = n1; n1 = n2; n2 = t; t = m1; m1 = m2; m2 = t; } int first = 1; for (long long i = 1; i * m2 < n2 * k; ++i) { // 严格落在区间内：大于左端点，小于右端点 if (i * m1 > n1 * k && gcd(i, k) == 1) { if (!first) { putchar(' '); } printf("%lld/%lld", i, k); first = 0; } } putchar('\n'); return 0; }

3.3 每一段代码为什么这样写

scanf里的格式"%lld/%lld %lld/%lld %lld"直接按分数格式读，斜杠是普通字符匹配，不需要额外处理空格，输入里的空格也能被正确跳过。

first标志位用来控制空格。先把第一个输出不带空格，之后每个输出前补一个空格，这样行尾就不会有多余空格了。很多人在这个细节上丢分，PAT对格式的要求非常死，行尾空格也会判Presentation Error。

循环从i = 1开始，因为分母K为正，i必须大于0才可能是正分数。左端点判断用了严格大于：

i * m1 > n1 * k

右端点判断用了严格小于：

i * m2 < n2 * k

两个都是严格号，因为题目要的是“它们之间”，不包含两个端点。如果把端点也输出，样例里7/18对应的?/12可能不存在，但其他测试点会暴露问题。

3.4 一个容易被忽略的long long细节

我最初写的是int版本，本地样例也没问题，提交后有一组数据答案错误，排查了很久才发现是乘法溢出。n1 * k这种运算，在n1接近10的5次方、k也接近10的5次方时，乘积已经到10的10次方，int最多存21亿多一点，直接变成负数或截断值。所以全链路用long long是最省心的选择。虽然题目没有明确给出数值上限，但谁也不想在溢出这种低级错误上被卡。

4. 我提交后踩过的坑：报错场景和规避方式

4.1 答案错误，但样例能过：端点被算进去了

我第一次写的是：

if (i * m1 >= n1 * k && i * m2 <= n2 * k)

这里的>=和<=把两个端点的分数也判成了合法候选。如果某一边端点恰好能被K通分成整数分子，就会多输出一项。比如左端点就是5/12，K=12时i=5会被包含进来，但题目要求的是区间内部，不应该输出它。这就是典型的“样例过了但隐藏测试挂了”。

修法很简单：把判断条件全部改成严格不等号。

4.2 交换分数时只交换了一部分变量

这个错误特别蠢但特别容易犯。我之前交换的时候只换了分子，忘了换分母，导致排序逻辑完全错乱。正确做法是分子和分母四个变量整体交换，或者用一个结构体：

typedef struct { long long n, m; } Fraction; Fraction a, b, t; if (a.n * b.m > b.n * a.m) { t = a; a = b; b = t; }

用结构体赋值可读性好很多，也不容易漏掉某个字段。

4.3 格式错误：行尾空格

输出格式上，PAT要求分数之间一个空格，行首尾不能有多余空格。如果直接在循环里printf("%lld/%lld ", i, k)，每个分数后面都带空格，最后一个分数后面那个空格会被判错。

用first标志位处理是最稳的。也可以用计数器统计已输出个数，判断是否第一个，效果一样。

4.4 边界情况与自测用例

我整理了一组自测数据，建议提交前先跑一遍，比盲改代码高效得多：

第五个用例可能不会出现在考场上，但能帮你确认K=1时代码不会崩溃，循环条件也能正确处理。

提示：自测时不要只盯着样例。把输入顺序颠倒、把分数改成假分数、把K设成极其接近某个候选分数的情况，逐个跑一遍，很多隐藏bug就现形了。

5. 顺藤摸瓜：同一类数学思维在乙级里反复出现

5.1 1037在霍格沃茨找零钱到底在考什么

如果你最近常在PAT圈子里逛，会看到“pat（乙级）1037 在霍格沃茨找零钱（c语言）”也是搜得很热的关键词。这道题的背景是《哈利·波特》里的货币体系：1加隆等于17银西可，1银西可等于29纳特。输入应付和实付，输出找零。

很多人的第一反应是逐位相减，然后处理借位，结果被17和29的进制折腾得够呛。但标准解法是先把所有钱统一换算成最小的“纳特”单位，做一次减法，再一层层除回去：

总纳特 = (加隆 * 17 + 银西可) * 29 + 纳特

然后差值依次除以17*29、除以29、取余，就能得到找零的加隆、银西可和纳特。

这和1062的交叉相乘是同一个思想：先把不同单位对齐，再做整数运算。1062是把两个分数的分母通过交叉相乘对齐，1037是把不同面额的货币通过换算成最小单位对齐。表面上一道题是分数，一道题是钱，底层思维完全一致。

5.2 分数和货币都是“单位换算”的变体

我在刷乙级的过程中发现，这类题有一个通用套路：看到比较、找零、换算，第一反应不是急着写循环，而是问自己——能不能把所有量归一到同一个基准？

• 分数比较的基准是“公共分母”，用交叉相乘代替通分。
• 货币找零的基准是“最小单位”，换算完再减。
• 时间换算也是同理，比如时、分、秒，全部转成秒，处理完再转回去。

如果你能把1062吃透，1037基本就是换个壳子的事。反过来也一样，做过1037的人，再看到1062的分数比较，也会本能地想到“先统一单位”。

5.3 刷题建议：把同类型题目放在一起对比

我的习惯是刷完一道题之后，把题号记在一个清单里，标注它考的数学模型。比如1062和1037都可以归到“单位对齐”这个模型下。下次再遇到类似题，先翻这个清单，思路会打开很多。

还可以自己给自己出变体题：比如把1062改成“输出包含两端点的所有最简分数”，只需要把两个严格不等号改成非严格；再比如改成“输出分母不超过K的所有最简分数”，那枚举分母的维度就得加一重。做这些变形不是为了应付考试，而是为了让边界条件在脑子里扎根。

6. 我刷1062沉淀下来的三个做题习惯

6.1 先回答三个问题再动手写码

现在做PAT题目，我读完题第一件事不是开编辑器，而是在草稿纸上写下三个问题：区间是否包含端点？输入顺序是否有保证？数值范围是否需要long long？

这三个问题对应了1062的三大坑。先回答它们再写代码，基本能避开一半以上的提交错误。我知道很多同学喜欢边写边想，但乙级题目的数据范围通常不会太大，真正的难度就在这些边界语义里。先把边界定清楚，写代码就是翻译工作，很轻松。

6.2 本地写个对拍小脚本验证

对于枚举类题目，我强烈建议本地做一次“对拍”。方法很简单：写一个用double暴力判断的纯朴素版本，再写一个提交用的正式版，用一个简单的C程序或者Python脚本随机生成大量小范围输入，对比两个程序的输出是否完全一致。

比如随机生成分子分母在1到20之间、K在2到20之间的数据，跑几百组。如果正式版和朴素版输出一致，就说明枚举范围和边界条件大概率没问题。1062这种题非常适合对拍，因为输出是有序序列，可以直接用字符串比较。

6.3 提交前跑一遍极端用例

最后一个习惯是提交前花一分钟跑极端用例。我常用的固定几组包括：K=1、两个分数非常接近、输入顺序颠倒、分数包含假分数。这些用例不一定都存在标准答案里，但跑一遍能让心里有底。

提示：如果你在考场或在线评测环境里看不到本地编译器，也可以直接用题目自带的样例跑完再人工分析边界。重点是养成“样例过了不算过”的意识，尤其对PAT这种喜欢卡边界的评测系统。

就我个人经验来说，PAT乙级很少考天马行空的算法，它反复检验的是基础功和细心程度，1062就是个非常典型的缩影。最后再分享一个小技巧：用scanf读这种"%lld/%lld"格式时，斜杠前后都不用加空格，输入里的空格也会被自动跳过；如果某次读不进去，先检查是不是把半角斜杠打成了全角字符。这种细节看起来不起眼，考场上能帮你省下五分钟。