PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: tabr
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
Given X and Y, repeat the following process while X \gt 0:
- If X\gt Y, swap X and Y.
- Otherwise, replace X and Y with Y-X and X.
What will be the final value of Y?
EXPLANATION:
Let’s look at what’s going on with the algorithm.
If X \gt Y, we swap X and Y, so it’s enough to only consider the case X \leq Y.
When X \leq Y, the numbers are replaced with Y-X and X.
However, this process of “subtract X from the larger number” will continue as long as X is itself the smaller number.
That is, “subtract X from Y” will be repeated k times, where k is the smallest number such that
Y - kX \lt X.
It’s not hard to observe that after this, Y will be replaced with Y\% X, i.e, the remainder when Y is divided by X.
This allows us to speed up the algorithm by replacing repeated subtractions with a single division (to find the remainder).
This simple-looking optimization immediately brings the runtime down to \mathcal{O}(\log\min(X, Y)), which is fast enough!
Why?
The key observation here is that every two moves, the minimum number at least halves.
Recall that we have X \leq Y.
After one move, we have (X, Y \bmod X).
After the second move, we have (Y\bmod X, X\bmod (Y\bmod X)).
It can be shown that X\bmod (Y\bmod X) is \leq \frac{X}{2} (in fact, a bit more generally, x\bmod y is always \leq \frac{x}{2} when y\leq x, see the first section of this page).
This way, the minimum at least halves every two moves; so within 2\log\min(X, Y) moves it’ll reach 0 at which point the algorithm terminates.
In fact, it can be observed that the given process is exactly the Euclidean algorithm to find the greatest common divisor of two positive integers!
So, you can just print \gcd(X, Y) as the answer, which most languages have in their math libraries.
TIME COMPLEXITY:
\mathcal{O}(\log\min(X, Y)) per testcase.
CODE:
Editorialist's code (Python)
import math
for _ in range(int(input())):
x, y = map(int, input().split())
print(math.gcd(x, y))