SUMDIV2 - Editorial

editorial
, ,
1

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

X\cdot(b+1) = Y\cdot(a+1)

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)
5 Likes
2

Is there a specific reason we need to first evaluate xy - x - y and then check if its less than zero before evaluating 5xy - x - y? For some reason, directly giving the answer directly as 5xy - x - y results in 2/4 wrong submissions(the last two are wrong), but the question states it can be any number and it doesn’t need to be the minimum.

The reason I ask is because during the competition, I gave the equivalent of 3xy - x - y as the answer, which should be correct for all test cases, but gives two wrong submissions.

1 Like
3

3xy - x - y, can get bigger than 1e18, when x,y are bigger numbers of the order 1e9.

So its better to use n = xy - x - y first to calculate the value of n.
Then check if it is lesser than 1, if it is then recalculate n using n = 3xy - x - y.

2 Likes
4

why we can not take a=2x-1 and b=2y-1 ?