题目描述
一个分数一般写成两个整数相除的形式：N/M，其中 M 不为0。最简分数是指分子和分母没有公约数的分数表示形式。
现给定两个不相等的正分数 N1/M1 和 N2/M2，要求你按从小到大的顺序列出它们之间分母为 K 的最简分数。
输入格式
输入在一行中按 N/M 的格式给出两个正分数，随后是一个正整数分母 K，其间以空格分隔。题目保证给出的所有整数都不超过 1000。
输出格式
在一行中按 N/M 的格式列出两个给定分数之间分母为 K 的所有最简分数，按从小到大的顺序，其间以 1 个空格分隔。行首尾不得有多余空格。题目保证至少有 1 个输出。
测试样例
Case 0:
输入
7/18 13/20 12
输出
5/12 7/12
Case 1:
输入（分数 1 比分数 2 大）
13/20 7/18 12
输出
5/12 7/12
Case 2:
输入（结果的分子分母必须互质）
1/2 1/3 16
输出
7/16
Java代码
/**********************************************************************************
Submit Time Status Score Problem Compiler Run Time User
8/17/2019, 22:17:02 Accepted 20 1062 Java (openjdk) 85 ms wowpH
**********************************************************************************/
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
private static boolean coPrime(int a, int b) { // 检查a和b是否互质
while (true) {
a = a % b;
if (0 == a) {
return 1 == b ? true : false;
}
b = b % a;
if (0 == b) {
return 1 == a ? true : false;
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] number = br.readLine().split(" "); // 三个数
String[] arr = number[0].split("/");
int N1 = Integer.parseInt(arr[0]);
int M1 = Integer.parseInt(arr[1]);
arr = number[1].split("/");
int N2 = Integer.parseInt(arr[0]);
int M2 = Integer.parseInt(arr[1]);
int K = Integer.parseInt(number[2]);
int min, max; // 开区间的范围
if (N1 * M2 < N2 * M1) { // 分数1比分数2小
min = K * N1 / M1 + 1; // 最小值
max = K * N2 / M2; // 最大值
if (K * N2 == max * M2) { // 最大值是等于右边界
max = max - 1; // 开区间
}
} else { // 分数1比分数2大
min = K * N2 / M2 + 1;
max = K * N1 / M1;
if (K * N1 == max * M1) {
max = max - 1;
}
}
for (int i = min, count = 0; i <= max; ++i) {
if (coPrime(K, i)) { // 互质
if (count > 0) { // 不是第一个分数
System.out.print(" "); // 分数前面输出空格
}
System.out.print(i + "/" + K);
++count;
}
}
}
}