MAKEMULTIPLE - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Utkarsh Gupta
Testers: Nishank Suresh, Takuki Kurokawa
Editorialist: Nishank Suresh

DIFFICULTY:

1163

PREREQUISITES:

None

PROBLEM:

Given two integers A and B, is it possible to add a non-negative integer K to both of them such that A+K is a divisor of B+K?

EXPLANATION:

First, if A = B, then the answer is obviously “Yes”.

Otherwise, note that no matter which K we choose, the difference between A and B remains constant.
Let d = B - A. A valid K exists if and only if A \leq d.

Proof

If A \leq d, then choose K = d - A.
This makes A = d and B = 2d, and of course A is now a factor of B.

Conversely, suppose A \gt d. Suppose, for some K, A+K is a factor of B+K. Then, there exists an x \geq 1 such that:

x\cdot (A+K) = B+K = A+d+K \implies (x-1)\cdot (A+K) = d

But A \gt d, so A+K \gt d. This means a valid only exists in the case when d = 0, when we can choose x = 1.
However, we assumed A \neq B, which implies d \neq 0, so this case cannot happen.

This completes the proof.

TIME COMPLEXITY

\mathcal{O}(1) per test case.

CODE:

Editorialist's code (Python)
for _ in range(int(input())):
    a, b = map(int, input().split())
    d = b - a
    print('Yes' if d == 0 or a <= d else 'No')
3 Likes

Hey Editor,
This code will fail on the testcase where a = 6; b = 31, this code will give us answer “YES”, but the actually answer should be “NO”. Please clear my doubt.
some other testcases like-
a = 7, b = 36
a = 8, b = 41

they are working
6+19=25 31+19=50
7+22=29 36+22=58
8+25=33 41+25=66

1 Like

@pranjalrajeev

Nothing wrong in the code.

For a = 6, b = 31, K = 19
For a = 7, b = 36, K = 22
For a = 8, b = 41, K = 25

Proof :

We have to find an integer K such that (B + K) / (A + K) = Q .
Where Q ∈ Integer and Q can be 1,2,3,4…,

Now let say Q = 2,
then, (B + K) / (A + K) = 2 and after solving you get K = B - 2A

Now, to check, replace K with B - 2A
B + (B - 2A ) / (A + B - 2A) = 2(B - A) / (B- A) = Integer

My submission CodeChef

1 Like