ADDGCD - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You have two integers X and Y. In one operation you can increase either one of them by 1.
Find the minimum number of operations needed to reach a state where \gcd(X, Y) \gt 1.

EXPLANATION:

Observe that if both X and Y are even, their GCD will also be even: which means it’ll definitely be \gt 1.

X can be made even using at most one operation, and the same holds for Y.
This means the answer is definitely \leq 2.
So, we only need to check if the answer can be 0 or 1.

That’s fairly easy:

  • If \gcd(X, Y) \gt 1, the answer is 0.
  • Otherwise, if \gcd(X+1, Y) \gt 1 or \gcd(X, Y+1) \gt 1, the answer is 1.
  • If all previous checks failed, the answer is 2.

The value of \gcd(X, Y) can be computed in \mathcal{O}(\log\min(X, Y)) time using the Euclidean algorithm.
Most languages have a gcd function in their library that implements this already (std::gcd in C++ and math.gcd in Python for example), so you can just use these existing implementations rather than writing your own.

TIME COMPLEXITY:

\mathcal{O}(\log\min(X, Y)) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    x, y = map(int, input().split())
    
    ans = 2
    from math import gcd
    for i in range(2):
        for j in range(2):
            if gcd(x+i, y+j) > 1: ans = min(ans, i+j)
    print(ans)
1 Like