我记得第一次刷到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/127/18约等于0.388913/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是左端点结果第一个测试点可能就过不了。排序也建议用交叉相乘而不是doubleif (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/40.75和5/41.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/12K12时i5会被包含进来但题目要求的是区间内部不应该输出它。这就是典型的“样例过了但隐藏测试挂了”。修法很简单把判断条件全部改成严格不等号。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 边界情况与自测用例我整理了一组自测数据建议提交前先跑一遍比盲改代码高效得多输入期望输出说明7/18 13/20 125/12 7/12官方样例基础验证1/2 3/2 43/4 5/4区间有大于1的分数验证枚举上界13/20 7/18 125/12 7/12输入顺序颠倒验证交换逻辑1/3 1/2 125/12中间有非最简分数如4/12、6/12验证gcd过滤1/2 3/2 11/1K1边界验证gcd(1,1)1和循环条件第五个用例可能不会出现在考场上但能帮你确认K1时代码不会崩溃循环条件也能正确处理。提示自测时不要只盯着样例。把输入顺序颠倒、把分数改成假分数、把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 提交前跑一遍极端用例最后一个习惯是提交前花一分钟跑极端用例。我常用的固定几组包括K1、两个分数非常接近、输入顺序颠倒、分数包含假分数。这些用例不一定都存在标准答案里但跑一遍能让心里有底。提示如果你在考场或在线评测环境里看不到本地编译器也可以直接用题目自带的样例跑完再人工分析边界。重点是养成“样例过了不算过”的意识尤其对PAT这种喜欢卡边界的评测系统。就我个人经验来说PAT乙级很少考天马行空的算法它反复检验的是基础功和细心程度1062就是个非常典型的缩影。最后再分享一个小技巧用scanf读这种%lld/%lld格式时斜杠前后都不用加空格输入里的空格也会被自动跳过如果某次读不进去先检查是不是把半角斜杠打成了全角字符。这种细节看起来不起眼考场上能帮你省下五分钟。