問題

$a,b,c,d$の4つの数が与えられます。$a < x \leq c$,$b < y \leq d$であり、$ab$で割り切れるような数$x$,$y$を求めてください。どれを出力しても良いです

考え方

題意より、$x \cdot y \equiv 0 \pmod{a \cdot b } $となるような$x$, $y$を求めればよく、整数$k$に対して$a \cdot b \cdot k = x \cdot y$はこれを満たします。$k$は$k = k_1 \cdot k_2$と任意の整数の積で表してよいです。

次に、$a \cdot b = e \cdot f$となる整数$e$, $f$を考えます。$e$は整数であることから$a \cdot b$を割り切れる数であるので$a \cdot b$の約数です。また、$f= \frac{a \cdot b}{e}$で示せます。$a \cdot b$の約数はこれは$a$と$b$ぞれぞれから約数を1つずつ選んだ時の積の集合と一致します。

例を挙げます。$a=3$, $b=4$としたとき、$a=3$, $b=2 \cdot 2$ で、$a \cdot b = 12 = e \cdot f$となるようなeは$1, 2, 4, 6, 12$が考えられます。これは$a$の約数$1,3$と$b$の約数$1,2,4$の集合の積となるます

ここで、$a \cdot b \cdot k = e \cdot f \cdot k = (e \cdot k_1) \cdot (f \cdot k_2) = x \cdot y$ として、$x = (e \cdot k_1)$, $y = (f \cdot k_2)$で表します。$k_1$, $k_2$は任意の整数をとれるので、$x$は$e$の倍数で、$y$は$f$の倍数です。$e$を列挙すれば、$e$は$f$から求められるので、$a < x \leq c$,$b < y \leq d$となる倍数を適当に選べば良いです。任意の組み合わせを1つ表示すればよいので、例えば、最も小さい数字を選んでよいです。

実装

補題として、ある数$a$以上の最小の$m$の倍数は次のように求められます。$ \lceil \frac{a}{m} \rceil m $。切り上げはceil(a,b) = (a+b-1) // bの式を使うと高速に計算できます
$e$は$a$の約数列挙と$b$の約数列挙を行いその積とします。$f$は$e$から算出します。
$e$, $f$から$x$, $y$を求めます。これは上記の式を用いて$a+1$, $c+1$以上の数を1つ選べばよいです。

ceil = lambda a, b: (((a) + ((b) - 1)) // (b))

def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    # divisors.sort()
    return divisors

q = int(input())
for _ in range(q):
    a, b, c, d = map(int, input().split())
    ab = a * b
    res = [-1, -1]
    DivAs = make_divisors(a)
    DivBs = make_divisors(b)
    for DivA in DivAs:
        for DivB in DivBs:
            e = DivA * DivB
            f = ab // e
            x = ceil(a + 1, e) * e
            if not (a < x <= c): continue
            y = ceil(b + 1, f) * f
            if not (b < y <= d): continue
            res = [x, y]
    print(*res)