Euclidean Algorithm — GCD
Practice this coding question on Coding Gurukul.
Problem statement
For each pair of nonnegative integers a and b, print their greatest common divisor (GCD) using the Euclidean algorithm. Repeatedly replace (a, b) with (b, a mod b) until b is 0. The remaining a is the answer. For this problem, gcd(0,0)=0. If exactly one value is 0, the answer is the other value. Use signed 64-bit integers. Worked example gcd(48,18)=6, gcd(0,7)=7, and gcd(13,17)=1.
Input format
First line: q. Next q lines: a b.
Output format
Print one greatest common divisor per line.
Constraints
1 <= q <= 100000; 0 <= a,b <= 10^18.
Sample input
3 48 18 0 7 13 17
Sample output
6 7 1
Sign in to run or submit a solution in C++, Java or Python.