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;

			}

		}

	}

}

巴特西