PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
You’re given values A, B, C.
You can do one of the following in one move:
- Set A \gets \gcd(A, C) and B \gets \gcd(B, C), or
- Increase C by 1.
Find the minimum number of moves needed to make A = B.
EXPLANATION:
The main observation is that the answer really can’t be very large.
In particular, it’s always possible to make A=B in 3 moves as follows:
- Set A \gets \gcd(A, C) and B\gets \gcd(B, C).
- Increment C by 1.
- Set A \gets \gcd(A, C) and B\gets \gcd(B, C) again.
This will always set both A and B to 1 no matter what the initial values of A, B, C are.
To see why, note that the final value of A will be exactly \gcd(A, C, C+1) (here we mean the initial value of C), because we took GCD with C and then later with C+1.
However there’s no integer larger than 1 that divides both C and C+1, so this GCD must equal 1.
Similarly, B becomes 1.
Since the answer is \le 3, we only need to check if 0, 1, 2 are possible - if none of them are, the answer is automatically 3.
We check each one in turn.
- ans = 0 is possible only if A = B initially.
- ans = 1 is possible only if \gcd(A, C) = \gcd(B, C), since that’s the only move which can modify A and B.
- If ans \ne 1, then ans = 2 is possible only when \gcd(A, C+1) = \gcd(B, C+1).
This is because with two moves the only new option we get is to increment and then take GCD - the other options are equivalent to what we can do with one move.
So, check each of the above cases, and if they all fail then the answer is 3.
To compute GCDs quickly, use the Euclidean algorithm. Most languages have a GCD function in their library that already does this (std::gcd or __gcd in C++ and math.gcd in Python, for example).
TIME COMPLEXITY:
\mathcal{O}(\log(\max(A, B, C))) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
a, b, c = map(int, input().split())
import math
if a == b: print(0)
elif math.gcd(a, c) == math.gcd(b, c): print(1)
elif math.gcd(a, c+1) == math.gcd(b, c+1): print(2)
else: print(3)