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:
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')