Hankson的趣味题JAVA版本

解题思路:

    首先， 我们通过题目应该知道 a1<= x <= b1，  如果以此范围暴力枚举 x ， 对于b1很大， a1很小的情况求解 x 可能会超时；

    因此，我们需要优化枚举的范围，我们可以把 x 的枚举范围改为：x*x<=b1 ；

    进一步优化求解两数最大公约数过程， 我们从数学公式中获知 x 与 y 的最大公约数如果为 k ， 则  x/k 与 y/k 的最大公约数为 1；由此可得 a0/a1 与 x/a1 的最大公约数为 1 ， b1/x 与 b1/b0 的最小公约数也为 1

    
注意事项:

    gcd方法为求解两数最大公约数的方法；

    每一组 arr 数组 中 arr[0],arr[1],arr[2],arr[3] 分别代表 a0,a1,b0,b1；

    findx方法的功能为获得某一组 arr 数组合理的 x 的个数

    

参考代码:

public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[][] arrs = new int[n][4];
		// 把数据存取到二维数组arrs中去
		for (int i = 0; i < n; i++) {
			arrs[i][0] = scanner.nextInt();
			arrs[i][1] = scanner.nextInt();
			arrs[i][2] = scanner.nextInt();
			arrs[i][3] = scanner.nextInt();
		}
		for (int i = 0; i < arrs.length; i++) {
//			调用函数
			System.out.println(findx(arrs[i]));
		}
	}

	public static int findx(int[] arr) {
		int num = 0;
		for (int i = 1; i * i <= arr[3]; i += arr[1]) {
			if (arr[3] % i == 0) {
				// 其中一个因子
				if ((i % arr[1]) == 0 && gcd(arr[0] / arr[1], i / arr[1]) == 1
						&& gcd(arr[3] / arr[2], arr[3] / i) == 1) {
					num++;
				}
				int j = arr[3] / i;// 得到另一个因子
				// 若两因数相等就跳到下一个数
				if (i == j)
					continue;
				if ((j % arr[1]) == 0 && gcd(arr[0] / arr[1], j / arr[1]) == 1
						&& gcd(arr[3] / arr[2], arr[3] / j) == 1) {
					num++;
				}

			}
		}

		return num;
	}

	public static int gcd(int x, int y) {

		// 辗转相除法递归完成求两个数的最大公约数
		return y == 0 ? x : gcd(y, x % y);
	}