Divisible Numbers (hard version)
Contest: Codeforces Round  828 (Div. 3)
Difficulty rating: 1900
Tags: brute force, math, number theory

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.

Input format:
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$$$).

Output format:
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.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
2 2
4 6
12 12
-1 -1
-1 -1
373248 730
-1 -1
15120 53760
-1 -1
536870912 536870912

Editorial:
Let's look at the slow solution first, which will lead us to the full one. Let's iterate over the number $$$x$$$ from $$$a + 1$$$ to $$$c$$$.
Given a number $$$x$$$, we want to find a $$$y$$$ from $$$b + 1$$$ to $$$d$$$ such that $$$x \cdot y$$$ is divisible by $$$a \cdot b$$$. Since $$$x \cdot y$$$ must be divisible by $$$a \cdot b$$$, the following conclusion can be drawn: $$$y$$$ must be divisible by $$$\frac{a \cdot b}{\gcd(a \cdot b, x) }$$$. Let's denote this number as $$$s$$$. Now our task is to check if there is a multiple of $$$s$$$ between $$$b + 1$$$ and $$$d$$$. The problem can be solved in many ways, you can simply consider the largest multiple of $$$s$$$ that does not exceed $$$d$$$ — it is equal to $$$\left \lfloor{\frac{d}{s}} \right \rfloor \cdot s$$$ We compare this number with $$$b + 1$$$, and if it matches, then we have found a suitable pair.
Now let's note that we do not need to iterate over all the values ​​of $$$x$$$, because from the number $$$x$$$ we are only interested in $$$\gcd(x, a \cdot b)$$$ — and this is one of the divisors of $$$a \cdot b$$$!
Even though the product $$$a \cdot b$$$ can be large, we can still consider all divisors of this number, since $$$a$$$ and $$$b$$$ themselves are up to $$$10^9$$$. Let's find the divisors of $$$a$$$ and $$$b$$$ separately, then notice that any divisor of $$$a \cdot b$$$ — is $$$a' \cdot b'$$$, where $$$a'$$$ — is some divisor $$$a$$$, and $$$b'$$$ — is some divisor $$$b$$$.
Let's calculate the running time. We need to factorize the numbers $$$a$$$ and $$$b$$$ into prime factors, this can be done in $$$O(\sqrt a)$$$. Next, you need to iterate over pairs of divisors $$$a$$$ and $$$b$$$. Recall the estimate for the number of divisors of a number (https://oeis.org/A066150): the number $$$x$$$ up to $$$10^9$$$ has no more than $$$1344$$$ divisors. Therefore, we can sort through the pairs for $$$1344^2$$$. We learned how to find the optimal $$$y$$$ for $$$O(1)$$$. We get that for each test case we have learned to solve the problem in $$$O(\sqrt a + (1344^2))$$$.