Preserve common divisors with Euclid
Replace a pair with a smaller equivalent pair until the remainder is zero.
Understand the idea
The common divisors of a and b are exactly those of b and a mod b. Replace (a,b) with (b,a mod b) while b is nonzero. For nonnegative inputs, the last nonzero value is the GCD.
Trace a small example
For (84,30), the pairs become (30,24), (24,6), (6,0), so the GCD is 6. Across a sequence keep g = gcd(g,x), starting with g = 0, since gcd(0,x) = x for nonnegative x.
#include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<long long> values{18, 30, 42};
long long g = 0;
for (long long value : values) g = std::gcd(g, value);
std::cout << g << '\n';
}Conditions and cost
Euclid uses O(log V) iterations for inputs bounded by V and constant iterative space. Define gcd(0,0) = 0 for this programming contract. Handle signs deliberately; the absolute value of the minimum signed integer may not fit.
Prefix sum explorer
Query [l, r] is zero-based and inclusive. P[k] stores the total of the first k values; P[0] is zero.
Input array a
Prefix array P
Preprocess once in O(n). Each range sum then takes O(1).
Guided simulation · Change the inputs to test your understanding.
Which next pair preserves gcd(84,30)?
Turn the idea into code
Find gcd of [18,30,42].
Give me a hint
Fold from left to right.
Show the explained solution
gcd(18,30) = 6 and gcd(6,42) = 6.
Your notes
Mark complete when you can explain it yourself.