Bahosain was trying to solve this simple problem, but he got a Runtime Error on one of the test cases, can you help him by solving it?
Given an array of N non-negative integers and an integer K, your task is to find two integers X and Y from the given array such that X × Y = K.
The chosen numbers must have different indices in the array.
Input
The first line of input contains T (1 ≤ T ≤ 128), the number of test cases.
The first line of each test case contains two integers: N (2 ≤ N ≤ 100,000) and K (1 ≤ K ≤ 100,000). The next line contains N space-separated integers, each between 0 and 100,000.
Output
For each test case, if there is no solution, print -1 on a single line. Otherwise print a single line with two space-separated integers X Y (X ≤ Y), where X and Y are two numbers from the given array and X × Y = K.
If there is more than one possible solution, print the one with the minimum X.
|
Sample Input |
Sample Output |
||
|
4 |
2 6 |
||
|
6 12 |
-1 |
||
|
3 6 2 |
4 2 |
9 |
3 12 |
|
2 1 |
1 12 |
||
|
1 2 |
|||
|
4 36 |
|||
|
12 18 |
3 36 |
||
|
4 12 |
|||
|
1 2 6 |
12 |
||
这道题说多了都是泪，在WA了几道题的情况下跑到这道题来写，还写得很快，导致区间分错，哎，以后要多注意开闭区间啊，天呐！！！！
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
using namespace std; const int MX = 111111;
int num[MX];
int n, k; bool judge(int i, int mid)
{
if (num[i] * num[mid] >= k) return true;
else return false;
} int main()
{
//freopen("input.txt", "r", stdin);
int cas;
while (scanf("%d", &cas) != EOF)
{
while(cas--)
{
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++)
{
scanf("%d", &num[i]);
}
sort(num, num + n);
bool j = true;
for (int i = 0; i < n; i++)
{
int lower = i + 1;//就是它= =
int higher = n - 1;//它以后也要多留心！！！
while (lower <= higher)
{
int mid = (lower + higher) / 2;
if (judge(i, mid)) higher = mid - 1;
else lower = mid + 1;
}
if (num[lower] * num[i] == k)
{
j = false;
printf("%d %d\n", num[i], num[lower]);
break;
}
}
if (j) printf("-1\n");
}
}
return 0;
}