問題
- $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)