PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: frtransform
Testers: mexomerf, rivalq
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given X and Y, find any positive integer N such that Y divides N+X and X divides N+Y.
EXPLANATION:
Let’s analyze what a valid N must look like.
- Y should divide N+X, which means N+X = aY for some positive integer a.
- X should divide N+Y, which means N+Y = bX for some positive integer b.
Putting these equations together, we see that N = aY-X = bX - Y, which reduces to
Our task is to choose appropriate a and b so that these equations are satisfied.
The simplest way to do this is to make both sides equal to XY, by choosing b = Y-1 and a = X-1.
This gives us N = aY-X = (X-1)Y - X = XY-X-Y.
However, note that we need to find a positive value of N, and the above value isn’t always positive.
In fact, it fails to be positive in exactly three cases: X = 1, Y = 1, or X = Y = 2.
For those three cases, we simply need to choose higher values of a and b.
For example, choose a = 3X-1 and b = 3Y-1 to obtain N = 3XY-X-Y.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase.
CODE:
Code (Python)
for _ in range(int(input())):
x, y = map(int, input().split())
ans = x*y - x - y
if ans <= 0: ans = 5*x*y - x - y
print(ans)