PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: still_me
Testers: the_hyp0cr1t3, rivalq
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
PROBLEM:
Find the maximum number of people who can split N apples and M oranges equally.
EXPLANATION:
Suppose there were k people. Then, for equal distribution, k must be a divisor of N and a divisor of M.
The largest such k is, by definition, \gcd(N, M); and this is the answer.
Finally, since N and M can be quite large, it’s necessary to compute \gcd(N, M) quickly. This can be done with the help of the Euclidean algorithm, or you can just use inbuilt functions corresponding to your language (std::gcd
in C++, math.gcd
in Python, and so on).
TIME COMPLEXITY:
\mathcal{O}(\log\min(a, b)) per testcase.
CODE:
Code (Python)
from math import gcd
for _ in range(int(input())):
n, m = map(int, input().split())
print(gcd(n, m))