【PAT乙级】1062 最简分数

一个分数一般写成两个整数相除的形式：N/M，其中 M 不为0。最简分数是指分子和分母没有公约数的分数表示形式。

现给定两个不相等的正分数 N​1​​/M​1​​ 和 N​2​​/M​2​​，要求你按从小到大的顺序列出它们之间分母为 K 的最简分数。

输入格式：

输入在一行中按 N/M 的格式给出两个正分数，随后是一个正整数分母 K，其间以空格分隔。题目保证给出的所有整数都不超过 1000。

输出格式：

在一行中按 N/M 的格式列出两个给定分数之间分母为 K 的所有最简分数，按从小到大的顺序，其间以 1 个空格分隔。行首尾不得有多余空格。题目保证至少有 1 个输出。

输入样例：

7/18 13/20 12

输出样例：

5/12 7/12

个人理解

本题有两种思路。

第一种

这种思路是直接找到最简分数分子的范围，通过begin = n1*k/m1 + 1【这个+1我一开始错误地处理成只在n1*k%m1 != 0的时候+1，导致第三个测试点一直过不去，后来突然意识到无论什么时候初始点都要在整除的结果上+1】，end = n2*k/m2【当n2*k) % m2 == 0时需要将end --】。然后直接在这个范围内进行gcd的检查即可。

题目中还有一个坑点就是N1/M1和N2/M2的大小不确定。

说明：使用这种思路是因为题目中其实没有规定是真分数【虽然测试数据都是真分数】，而且比进行遍历优化了一些【虽然只优化了一点点】。

代码实现

#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <algorithm> #include <iostream> #define ll long long #define ep 1e-5 #define INF 0x7FFFFFFF int const maxn = 1005; using namespace std; //寻找最大公约数 int gcd(int a, int b) { if (b == 0) return a; a = abs(a); b = abs(b); return gcd(b, a%b); } int main() { //初始化 int n1, m1, n2, m2, k, cnt = 0; //输入 scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k); //Calculate if (n1*m2 > n2*m1) { swap(n1, n2); swap(m1, m2); } //找到范围 int begin = n1*k/m1 + 1, end = n2*k/m2; if ((n2*k) % m2 == 0) { end --; } //在范围内寻找并输出 for (int i = begin; i <= end; i ++) { if (gcd(i, k) == 1) { if (cnt != 0) cout << " "; cout << i << "/" << k; cnt ++; } } return 0; }

第二种

这种思路其实就是在真分数的范围内进行遍历寻找，满足gcd == 1的最简真分数输出即可。

说明：这种方法是我在第一种想法一直AC不过的时候重写的，然后AC了，后来不甘心第一种怎么会出错，结果可以用来测试，最后通过它找到了第一种思路中的bug。

代码实现

#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <algorithm> #include <iostream> #define ll long long #define ep 1e-5 #define INF 0x7FFFFFFF int const maxn = 1005; using namespace std; //寻找最大公约数 int gcd(int a, int b) { if (b == 0) return a; a = abs(a); b = abs(b); return gcd(b, a%b); } int main() { //初始化 int n1, m1, n2, m2, k, cnt = 0; //输入 scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k); //Calculate if (double(1.0*n1/m1) > double(1.0*n2/m2)) { swap(n1, n2); swap(m1, m2); } for (int i = 1; i < k; i ++) { //下列两种边界条件方法都可以，乘法可以避免浮点转化的问题 //if (i > 1.0*n1*k/m1 && i < 1.0*n2*k/m2 && gcd(i,k) == 1) { if (i*m1 > n1*k && i*m2 < n2*k && gcd(i, k) == 1) { if (cnt != 0) cout << " "; cout << i << "/" << k; cnt ++; } } return 0; }

总结

学习不息，继续加油