构造二阶行列式

题目描述

小欧希望你构造一个二阶行列式，满足行列式中每个数均为不超过 20 的正整数，且行列式的值恰好等于x。你能帮帮她吗?

输入描述

一个正整数x。-1000 <= x <= 1000

输出描述

如果无解，请输出-1。否则输出任意合法行列式即可(输出两行,每行输出两个不超过20的正整数)。

输入示例

2

输出示例

3 2
5 4

提示信息

输出：

3 4

7 10

也是满足条件的。

思路：

这道题a、b、c、d每个数都为20以内的正整数，直接采用暴力对4个数进行遍历即可。若是想降低时间复杂度，可以按照多数之和解题的思想，遍历其中三个数剩下的一个采用二分的方法

注意二分的写法，代码为左闭右闭的二分写法

import java.lang.*;
import java.util.Scanner;
​
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int target = in.nextInt();int a, b, c, d;
​
​for (a = 1; a <= 20; a++) {for (d = 20; d >=a; d--) {if(a*d<=target)continue;for (b = 1; b <= 20; b++) {int start = 1;int end = 20;while (start < end) {c = (start + end) / 2;if(a*d-b*c<=target){end = c;}else{start = c+1;}}if(start == end && a*d-b*start==target){System.out.println(a+" "+b);System.out.println(start+" "+d);return;}}}}System.out.println(-1);}
}
​