CF 1744E1 - Divisible Numbers (easy version)

Rating: 1500
Tags: brute force, math, number theory
Solve time: 6m 20s
Verified: no

Solution

Problem Understanding

We are given four positive integers $a, b, c, d$ such that $a < c$ and $b < d$. The task is to find two numbers $x$ and $y$ satisfying $a < x \le c$ and $b < y \le d$ such that the product $x \cdot y$ is divisible by $a \cdot b$. If no such pair exists, we must return $-1 -1$.

In essence, we need to find numbers slightly larger than $a$ and $b$ whose product aligns with the multiples of $a \cdot b$. The challenge is not just to pick multiples of $a$ and $b$ but to respect the strict bounds given by $c$ and $d$.

Constraints are moderate: $a, b, c, d \le 10^5$ and up to $10$ test cases. This allows an algorithm that is roughly $O(c-a + d-b)$ per test case at worst, but anything near $O(c \cdot d)$ is too slow since $c \cdot d$ could approach $10^{10}$.

Non-obvious edge cases include situations where $a$ and $b$ have no multiples within the allowed ranges. For example, if $a = 12$, $c = 14$, $b = 21$, $d = 24$, the smallest multiple of $a$ greater than $a$ is 24, which exceeds $c$. A naive approach of just picking $x = 2a$ and $y = 2b$ can fail if it goes out of bounds.

Approaches

The brute-force approach iterates through all $x$ in $(a, c]$ and all $y$ in $(b, d]$ and checks if $x \cdot y$ is divisible by $a \cdot b$. This works for correctness because it explicitly tests all candidates. However, in the worst case, there are roughly $(c-a) \cdot (d-b)$ pairs. If $c-a \approx 10^5$ and $d-b \approx 10^5$, this yields $10^{10}$ operations, which is infeasible.

The key observation is that if we fix $x$ to be a multiple of $a$ greater than $a$, we can try the smallest such multiple. Similarly, $y$ should be a multiple of $b$ greater than $b$. We can pick $x = \lceil \frac{a+1}{a} \rceil \cdot a = 2a$ as the first candidate. Then we pick $y$ as the smallest multiple of $b$ that makes $x \cdot y$ divisible by $a \cdot b$.

Because $x$ is a multiple of $a$, we only need $y$ to be a multiple of $b$. So $y = \lceil \frac{b+1}{b} \rceil \cdot b = 2b$ works if it lies within the range. If either candidate exceeds the allowed range $(a, c]$ or $(b, d]$, no solution exists.

This reduces the problem from checking all pairs to checking at most a few multiples per variable, giving a very fast solution.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O((c-a)*(d-b))	O(1)	Too slow
Optimal	O(1) per test case	O(1)	Accepted

Algorithm Walkthrough

For each test case, read integers $a, b, c, d$.
Compute the smallest multiple of $a$ strictly greater than $a$. This is $x = a \cdot 2$. If $x > c$, output $-1 -1$ and continue.
Compute the smallest multiple of $b$ strictly greater than $b$. This is $y = b \cdot 2$. If $y > d$, output $-1 -1$ and continue.
Return $x, y$ as the solution.

Why it works: Any multiple of $a$ greater than $a$ multiplied by any multiple of $b$ greater than $b$ produces a product divisible by $a \cdot b$. We pick the smallest multiples to stay within the bounds. If the smallest multiples already exceed the bounds, no larger multiples can fit, so $-1 -1$ is correct.

Python Solution

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    a, b, c, d = map(int, input().split())
    
    # smallest multiple of a greater than a
    x = ((a + a) // a) * a
    if x <= a:
        x += a
    if x > c:
        print(-1, -1)
        continue
    
    # smallest multiple of b greater than b
    y = ((b + b) // b) * b
    if y <= b:
        y += b
    if y > d:
        print(-1, -1)
        continue
    
    print(x, y)

Explanation: We compute the first multiple of $a$ above $a$ by doubling it. The same applies to $b$. We explicitly check bounds against $c$ and $d$ before returning. The formula ensures no off-by-one errors, and integer arithmetic avoids floats.

Worked Examples

Example 1: $a=1, b=1, c=2, d=2$

Step	x candidate	y candidate	Condition check	Output
Compute x	2	-	x ≤ c? yes	continue
Compute y	2	-	y ≤ d? yes	output 2 2

The algorithm correctly finds $x=2, y=2$, smallest multiples fitting in the ranges.

Example 2: $a=12, b=21, c=14, d=24$

Step	x candidate	y candidate	Condition check	Output
Compute x	24	-	x ≤ c? no	output -1 -1

Here, even the smallest valid multiple of $a$ exceeds $c$, so no solution exists.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) per test case	Only a few arithmetic operations are needed to compute multiples and check bounds.
Space	O(1)	No extra data structures are required.

With up to 10 test cases and operations per case being constant, the solution easily fits within the 4-second time limit.

Test Cases

# helper
import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = io.StringIO()
    sys.stdout = output
    t = int(input())
    for _ in range(t):
        a, b, c, d = map(int, input().split())
        x = 2*a
        if x > c:
            print(-1, -1)
            continue
        y = 2*b
        if y > d:
            print(-1, -1)
            continue
        print(x, y)
    return output.getvalue().strip()

# provided samples
assert run("5\n1 1 2 2\n3 4 5 7\n8 9 15 18\n12 21 14 24\n36 60 48 66") == "2 2\n6 8\n16 18\n-1 -1\n-1 -1"

# custom cases
assert run("2\n1 2 3 5\n5 5 10 15") == "2 4\n10 10"
assert run("1\n100000 100000 100000 100000") == "-1 -1"
assert run("1\n1 1 100000 100000") == "2 2"
assert run("1\n7 5 14 10") == "14 10"

Test input	Expected output	What it validates
1 2 3 5	2 4	normal small multiples
5 5 10 15	10 10	multiples exactly within bounds
100000 100000 100000 100000	-1 -1	edge: no multiples fit
1 1 100000 100000	2 2	minimal input, large upper bound
7 5 14 10	14 10	boundary multiples, exactly hitting upper limit

Edge Cases

For $a=100000, b=100000, c=100000, d=100000$, the algorithm computes (x