PAT(B) 1062 最简分数（Java）

题目链接：1062 最简分数 (20 point(s))

题目描述

一个分数一般写成两个整数相除的形式：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;
			}
		}
	}
}