Divisible Numbers (hard version)

题意翻译

给出四个整数 $a, b, c, d$, 请你构造一对整数 $(x, y)$, 满足： - $a < x\leq c$, $b<y\leq d$ - $x\times y$ 是 $a \times b$ 的倍数 若不存在，输出 $-1$ 数据范围： 简单版：$1\leq a < c \leq 10^5, 1\leq b<d\leq 10^5$ 困难版：$1\leq a < c \leq 10^9, 1\leq b<d\leq 10^9$ 其中，单个测试点中包含不超过 $10$ 组数据

题目描述

This is an hard version of the problem. The only difference between an easy and a hard version is the constraints on $ a $ , $ b $ , $ c $ and $ d $ . You are given $ 4 $ positive integers $ a $ , $ b $ , $ c $ , $ d $ with $ a < c $ and $ b < d $ . Find any pair of numbers $ x $ and $ y $ that satisfies the following conditions: - $ a < x \leq c $ , $ b < y \leq d $ , - $ x \cdot y $ is divisible by $ a \cdot b $ . Note that required $ x $ and $ y $ may not exist.

输入输出格式

输入格式

The first line of the input contains a single integer $ t $ $ (1 \leq t \leq 10 $ ), the number of test cases. The descriptions of the test cases follow. The only line of each test case contains four integers $ a $ , $ b $ , $ c $ and $ d $ ( $ 1 \leq a < c \leq 10^9 $ , $ 1 \leq b < d \leq 10^9 $ ).

输出格式

For each test case print a pair of numbers $ a < x \leq c $ and $ b < y \leq d $ such that $ x \cdot y $ is divisible by $ a \cdot b $ . If there are multiple answers, print any of them. If there is no such pair of numbers, then print -1 -1.

输入输出样例

输入样例 #1

10
1 1 2 2
3 4 5 7
8 9 15 18
12 21 14 24
36 60 48 66
1024 729 373248 730
1024 729 373247 730
5040 40320 40319 1000000000
999999999 999999999 1000000000 1000000000
268435456 268435456 1000000000 1000000000

输出样例 #1

2 2
4 6
12 12
-1 -1
-1 -1
373248 730
-1 -1
15120 53760
-1 -1
536870912 536870912

题目大意：
这个题目是“可除数”问题的困难版本。问题要求给定四个正整数 \(a, b, c, d\)，其中 \(a < c\) 和 \(b < d\)，需要找到一对数 \(x\) 和 \(y\) 满足以下条件：

- \(a < x \leq c\)，\(b < y \leq d\)，
- \(x \times y\) 能被 \(a \times b\) 整除。

如果这样的数对不存在，则输出 -1。

输入输出数据格式：
- 输入格式：第一行是一个整数 \(t\)（\(1 \leq t \leq 10\)），表示测试用例的数量。接下来每行包含四个整数 \(a, b, c, d\)（\(1 \leq a < c \leq 10^9\)，\(1 \leq b < d \leq 10^9\)）。
- 输出格式：对于每个测试用例，输出一对满足条件的数 \(x\) 和 \(y\)，如果有多组答案，输出其中任意一组。如果不存在这样的数对，则输出 -1 -1。

输入输出样例：
- 输入样例 #1：
```
10
1 1 2 2
3 4 5 7
8 9 15 18
12 21 14 24
36 60 48 66
1024 729 373248 730
1024 729 373247 730
5040 40320 40319 1000000000
999999999 999999999 1000000000 1000000000
268435456 268435456 1000000000 1000000000
```
- 输出样例 #1：
```
2 2
4 6
12 12
-1 -1
-1 -1
373248 730
-1 -1
15120 53760
-1 -1
536870912 536870912
```题目大意： 这个题目是“可除数”问题的困难版本。问题要求给定四个正整数 \(a, b, c, d\)，其中 \(a < c\) 和 \(b < d\)，需要找到一对数 \(x\) 和 \(y\) 满足以下条件： - \(a < x \leq c\)，\(b < y \leq d\)， - \(x \times y\) 能被 \(a \times b\) 整除。 如果这样的数对不存在，则输出 -1。 输入输出数据格式： - 输入格式：第一行是一个整数 \(t\)（\(1 \leq t \leq 10\)），表示测试用例的数量。接下来每行包含四个整数 \(a, b, c, d\)（\(1 \leq a < c \leq 10^9\)，\(1 \leq b < d \leq 10^9\)）。 - 输出格式：对于每个测试用例，输出一对满足条件的数 \(x\) 和 \(y\)，如果有多组答案，输出其中任意一组。如果不存在这样的数对，则输出 -1 -1。 输入输出样例： - 输入样例 #1： ``` 10 1 1 2 2 3 4 5 7 8 9 15 18 12 21 14 24 36 60 48 66 1024 729 373248 730 1024 729 373247 730 5040 40320 40319 1000000000 999999999 999999999 1000000000 1000000000 268435456 268435456 1000000000 1000000000 ``` - 输出样例 #1： ``` 2 2 4 6 12 12 -1 -1 -1 -1 373248 730 -1 -1 15120 53760 -1 -1 536870912 536870912 ```