GCD Variations
Pillar: Shape — "GCD of a subarray can only take at most \(O(\log \max)\) distinct values as you extend the subarray — the sequence of GCDs is a decreasing staircase."
Pillar: Set — "GCD is a monoid (associative, identity is \(0\)). Any data structure that stores monoid products — segment tree, sparse table — can answer GCD range queries."
The Setup
You know how to compute \(\gcd(a, b)\) for two numbers. But contest problems rarely ask for the GCD of two numbers. They ask for the GCD of an array, the GCD of every subarray, or the GCD of arbitrary ranges — possibly with updates.
Take the array \([12, 18, 24, 36]\). What's the GCD of the whole thing? You fold left to right:
The answer is \(6\). Straightforward. But now: how many distinct GCD values appear across all contiguous subarrays? There are \(\binom{4}{2} + 4 = 10\) subarrays. Do you need to compute all of them individually?
No. The GCD has a structural property — it forms a staircase — that lets you answer this question far more efficiently than brute force. That property is the star of this lesson.
GCD of an Array: Fold/Reduce
The GCD of \(n\) numbers is computed by folding:
This works because \(\gcd\) is associative: the grouping doesn't matter. \(\gcd(\gcd(a, b), c) = \gcd(a, \gcd(b, c))\). You can fold left, fold right, or split the array in half and combine — the result is the same.
The identity element is \(0\): \(\gcd(a, 0) = a\) for all \(a\). This makes \((\mathbb{Z}_{\geq 0}, \gcd, 0)\) a monoid — a set with an associative binary operation and an identity element. You saw monoids in Ch1 L2 (Numbers Are Sets). Addition is a monoid with identity \(0\). Multiplication is a monoid with identity \(1\). GCD is a monoid with identity \(0\).
Why does the identity matter? Because it means an empty range has a well-defined GCD: \(0\). And it means you can build any fold-based data structure (segment tree, sparse table) on top of GCD without special-casing empty nodes.
int gcdOfArray(vector<int>& values) {
int totalGCD = 0;
for (int element : values) {
totalGCD = __gcd(totalGCD, element);
}
return totalGCD;
}
\(O(n \log \max)\) time (each \(\gcd\) call costs \(O(\log \max)\)), \(O(1)\) space.
The Staircase Property
This is the key insight of the lesson. Trace this by hand and the rest of the lesson falls out.
The Claim
Fix a left endpoint \(i\). Define \(g(i, j) = \gcd(a_i, a_{i+1}, \ldots, a_j)\) for \(j \geq i\). As \(j\) increases from \(i\) to \(n-1\):
- \(g(i, j)\) can only decrease or stay the same — it never increases.
- Each time \(g(i, j)\) decreases, it drops by at least a factor of \(2\) (it loses a prime factor or reduces an exponent).
- Therefore \(g(i, j)\) takes at most \(O(\log_2(a_i))\) distinct values across all \(j\).
Why It Can Only Decrease
\(g(i, j+1) = \gcd(g(i, j),\; a_{j+1})\). Taking a GCD with a new element can only remove prime factors (or reduce exponents) from the running GCD — it can never add new ones. In the multiset picture: \(g(i, j)\)'s prime multiset is already the intersection of \(a_i, \ldots, a_j\)'s multisets. Adding \(a_{j+1}\) to the intersection can only shrink it further.
Why Each Drop Is Significant
When \(g(i, j)\) decreases, it must lose at least one prime factor or reduce some prime's exponent. Since \(a_i\) has at most \(\lfloor \log_2(a_i) \rfloor\) total prime factors (counting multiplicity) — because \(2^k \leq a_i\) means \(k \leq \log_2(a_i)\) — the GCD can decrease at most \(\lfloor \log_2(a_i) \rfloor\) times before hitting \(1\) (or stabilizing at some value that divides all remaining elements).
Concrete Trace
Array: \([48, 36, 24, 18, 12, 8]\)
Fix left endpoint \(i = 0\) (value \(48 = 2^4 \times 3\)). Extend \(j\) from \(0\) to \(5\):
| \(j\) | \(a_j\) | \(g(0, j)\) | Changed? | Prime factorization of GCD |
|---|---|---|---|---|
| \(0\) | \(48\) | \(48\) | — | \(2^4 \times 3^1\) |
| \(1\) | \(36\) | \(\gcd(48, 36) = 12\) | Yes | \(2^2 \times 3^1\) |
| \(2\) | \(24\) | \(\gcd(12, 24) = 12\) | No | \(2^2 \times 3^1\) |
| \(3\) | \(18\) | \(\gcd(12, 18) = 6\) | Yes | \(2^1 \times 3^1\) |
| \(4\) | \(12\) | \(\gcd(6, 12) = 6\) | No | \(2^1 \times 3^1\) |
| \(5\) | \(8\) | \(\gcd(6, 8) = 2\) | Yes | \(2^1\) |
The GCD takes exactly \(4\) distinct values: \(48, 12, 6, 2\). That's a staircase — flat plateaus separated by drops. The staircase has \(4\) steps, and \(48\) has \(\lfloor \log_2(48) \rfloor = 5\) total prime factors (four \(2\)s and one \(3\)), so \(4\) steps is well within the \(O(\log \max)\) bound.
Watch what happens at each drop: - \(48 \to 12\): lost two copies of \(2\) (exponent went from \(4\) to \(2\)). - \(12 \to 6\): lost one copy of \(2\) (exponent went from \(2\) to \(1\)). - \(6 \to 2\): lost one copy of \(3\) (exponent went from \(1\) to \(0\)).
Each drop removes at least one prime factor from the multiset. Once you see this, the \(O(\log \max)\) bound is obvious.
Application: Count Distinct Subarray GCDs
Problem: Given an array of \(n\) positive integers, how many distinct values appear among \(\gcd(a_i, \ldots, a_j)\) across all \(\binom{n}{2} + n\) contiguous subarrays?
Naive approach: Enumerate all \(O(n^2)\) subarrays, compute GCD for each, store in a set. \(O(n^2 \log \max)\) time. For \(n = 10^5\), that's \(10^{10}\) operations — way too slow.
Staircase approach: For each left endpoint \(i\), there are at most \(O(\log \max)\) distinct GCD values. So across all \(n\) left endpoints, the total number of distinct (endpoint, GCD value) pairs is \(O(n \log \max)\). You maintain a set of "active" GCD values from the previous column and update it.
The algorithm: maintain a set of GCD values that are currently "alive" from subarrays ending at \(j-1\). When you move to position \(j\), take the GCD of each alive value with \(a_j\), and also start a new subarray with just \(a_j\). Duplicates collapse. The set size stays \(O(\log \max)\) at each step.
int countDistinctSubarrayGCDs(vector<int>& values) {
int arraySize = values.size();
set<int> allDistinctGCDs;
set<int> previousEndpointGCDs;
for (int right = 0; right < arraySize; right++) {
set<int> currentEndpointGCDs;
currentEndpointGCDs.insert(values[right]);
for (int gcdValue : previousEndpointGCDs) {
currentEndpointGCDs.insert(__gcd(gcdValue, values[right]));
}
for (int gcdValue : currentEndpointGCDs) {
allDistinctGCDs.insert(gcdValue);
}
previousEndpointGCDs = currentEndpointGCDs;
}
return allDistinctGCDs.size();
}
Why it's correct. previousEndpointGCDs holds all distinct values of \(g(i, j-1)\) across every left endpoint \(i\). When you extend to \(j\), each of those becomes \(\gcd(g(i, j-1), a_j) = g(i, j)\). You also start the new subarray \([j, j]\) with value \(a_j\). The set automatically deduplicates.
Complexity. At each position \(j\), previousEndpointGCDs has at most \(O(\log \max)\) elements (staircase property). So the inner loop does \(O(\log \max)\) GCD computations per position, each costing \(O(\log \max)\). Total: \(O(n \log^2 \max)\).
For \(n = 2 \times 10^5\) and \(\max = 10^9\): \(2 \times 10^5 \times 30^2 \approx 1.8 \times 10^8\). Tight but feasible.
Optimization. An early exit helps: if the running GCD hits \(1\), no further extension from this left endpoint can produce a new value (since \(\gcd(1, x) = 1\) for all \(x\)). The inner loop for that left endpoint terminates immediately.
GCD Range Queries: Segment Tree
GCD is a monoid. Segment trees work for any monoid. So a GCD segment tree works out of the box — no clever modifications needed.
The combine function is just __gcd(a, b). The identity (for empty/out-of-range nodes) is \(0\).
Build: \(O(n)\) — each node stores the GCD of its range. Query: \(O(\log n)\) — standard segment tree range query. Update: \(O(\log n)\) — standard point update, recompute GCD up the path.
struct GCDSegmentTree {
int treeSize;
vector<int> tree;
void build(vector<int>& values) {
treeSize = values.size();
tree.assign(4 * treeSize, 0);
buildRecursive(values, 1, 0, treeSize - 1);
}
void buildRecursive(vector<int>& values, int node, int start, int end) {
if (start == end) {
tree[node] = values[start];
return;
}
int mid = (start + end) / 2;
buildRecursive(values, 2 * node, start, mid);
buildRecursive(values, 2 * node + 1, mid + 1, end);
tree[node] = __gcd(tree[2 * node], tree[2 * node + 1]);
}
int query(int node, int start, int end, int left, int right) {
if (right < start || end < left) return 0;
if (left <= start && end <= right) return tree[node];
int mid = (start + end) / 2;
return __gcd(query(2 * node, start, mid, left, right),
query(2 * node + 1, mid + 1, end, left, right));
}
int query(int left, int right) {
return query(1, 0, treeSize - 1, left, right);
}
void update(int node, int start, int end, int position, int newValue) {
if (start == end) {
tree[node] = newValue;
return;
}
int mid = (start + end) / 2;
if (position <= mid) update(2 * node, start, mid, position, newValue);
else update(2 * node + 1, mid + 1, end, position, newValue);
tree[node] = __gcd(tree[2 * node], tree[2 * node + 1]);
}
void update(int position, int newValue) {
update(1, 0, treeSize - 1, position, newValue);
}
};
\(O(n)\) build, \(O(\log n)\) per query and update (each GCD call is \(O(\log \max)\), so more precisely \(O(\log n \cdot \log \max)\) per operation).
When to use: you need GCD range queries AND the array changes (point updates).
Sparse Table for Static GCD Queries
Here's the trick. GCD is not just associative — it's also idempotent: \(\gcd(a, a) = a\). This means overlapping ranges don't corrupt the answer. You can compute \(\gcd(\text{range}[l, m])\) and \(\gcd(\text{range}[m', r])\) where the two ranges overlap, take \(\gcd\) of the results, and still get the correct answer.
Idempotency is exactly what a sparse table needs for \(O(1)\) queries. The idea: precompute \(\gcd\) for every range of length \(2^k\), then answer any query \([l, r]\) by overlapping two precomputed ranges that together cover \([l, r]\).
Define \(\text{table}[k][i] = \gcd(a_i, a_{i+1}, \ldots, a_{i + 2^k - 1})\).
Build: For \(k = 0\), \(\text{table}[0][i] = a_i\). For \(k > 0\):
Query \([l, r]\): Let \(k = \lfloor \log_2(r - l + 1) \rfloor\). Then:
The two ranges \([l, l + 2^k - 1]\) and \([r - 2^k + 1, r]\) overlap in the middle, but because \(\gcd\) is idempotent, that's perfectly fine.
struct GCDSparseTable {
vector<vector<int>> table;
vector<int> logTable;
void build(vector<int>& values) {
int arraySize = values.size();
int maxLog = __lg(arraySize) + 1;
table.assign(maxLog, vector<int>(arraySize, 0));
logTable.assign(arraySize + 1, 0);
for (int i = 2; i <= arraySize; i++) {
logTable[i] = logTable[i / 2] + 1;
}
for (int i = 0; i < arraySize; i++) {
table[0][i] = values[i];
}
for (int power = 1; power < maxLog; power++) {
for (int i = 0; i + (1 << power) - 1 < arraySize; i++) {
table[power][i] = __gcd(table[power - 1][i],
table[power - 1][i + (1 << (power - 1))]);
}
}
}
int query(int left, int right) {
int power = logTable[right - left + 1];
return __gcd(table[power][left], table[power][right - (1 << power) + 1]);
}
};
\(O(n \log n)\) build, \(O(1)\) query.
When to use: the array is static (no updates), and you need to answer many GCD range queries. If you have updates, use the segment tree instead.
Comparison table:
| Structure | Build | Query | Update | Requirement |
|---|---|---|---|---|
| Segment tree | \(O(n)\) | \(O(\log n)\) | \(O(\log n)\) | Associative (monoid) |
| Sparse table | \(O(n \log n)\) | \(O(1)\) | N/A | Associative + idempotent |
GCD satisfies both requirements, so you get to choose. Most contest problems with GCD range queries and updates call for the segment tree. Problems with no updates and many queries favor the sparse table.
Coprimality
Two integers \(a\) and \(b\) are coprime (or relatively prime) if \(\gcd(a, b) = 1\). In the multiset picture: their prime multisets don't intersect. They share no common prime factor.
Examples: - \(\gcd(8, 15) = \gcd(2^3, 3 \times 5) = 1\). Coprime — the sets \(\{2\}\) and \(\{3, 5\}\) are disjoint. - \(\gcd(12, 35) = \gcd(2^2 \times 3, 5 \times 7) = 1\). Coprime. - \(\gcd(12, 18) = 6 \neq 1\). Not coprime — they share factors \(2\) and \(3\).
Coprimality is not about the numbers being prime themselves. \(8\) and \(15\) are both composite, but they're coprime to each other.
Key identity. If \(\gcd(a, b) = 1\), then \(\text{lcm}(a, b) = a \times b\). When the multisets don't intersect, the union is just the concatenation. This identity shows up constantly in problems involving LCM.
Where coprimality leads. The concept of "how many integers from \(1\) to \(n\) are coprime to \(n\)" is Euler's totient function \(\phi(n)\) — the subject of Ch4. And counting coprime pairs in a range is a classic inclusion-exclusion problem in Ch6. This lesson gives you the definition; those chapters give you the machinery.
Common Mistakes
-
Using the wrong identity element. The identity for GCD is \(0\), not \(1\). \(\gcd(a, 0) = a\) for all \(a \geq 0\). If you initialize your segment tree or fold with \(1\) instead of \(0\), you'll get wrong answers whenever the true GCD is not a divisor of your initial value. Some implementations use a very large number as the identity — that works for min, but not for GCD.
-
Forgetting idempotency when choosing a data structure. If a problem gives you static GCD queries and you reach for a segment tree, you're paying \(O(\log n)\) per query when you could pay \(O(1)\) with a sparse table. Not wrong, but wasteful — and in tight time limits, it matters.
-
Assuming the staircase has \(O(\log n)\) steps. The bound is \(O(\log \max)\) — it depends on the value of the array elements, not the array length. For an array of length \(10^5\) where every element is \(2^{30}\), the staircase from any starting point has at most one step (everything is the same). But for an array of length \(3\) with elements \([2^{30}, 3^{19}, 1]\), the GCD changes at every step. The staircase length tracks the number of prime factors in the starting element, which is \(O(\log \max)\).
Quick Recap
- GCD of an array is a monoid fold. Identity is \(0\). Associativity means any grouping works — segment trees, sparse tables, divide-and-conquer all apply.
- The staircase property: fixing the left endpoint, the running GCD takes at most \(O(\log \max)\) distinct values as you extend right. Each drop removes at least one prime factor.
- Counting distinct subarray GCDs runs in \(O(n \log^2 \max)\) by maintaining a set of active GCD values per right endpoint.
- Segment tree gives \(O(\log n)\) range GCD queries with \(O(\log n)\) updates. Use when the array changes.
- Sparse table gives \(O(1)\) range GCD queries (no updates) because GCD is idempotent. Use for static arrays.
- Coprime means \(\gcd(a, b) = 1\) — disjoint prime multisets. This definition feeds directly into Euler's totient (Ch4) and coprime counting (Ch6).
Problems
| Problem | Link | Difficulty | Focus |
|---|---|---|---|
| CF 1349A — Orac and LCM | codeforces.com/problemset/problem/1349/A | Medium | GCD/LCM of all pairwise values; uses suffix GCD array |
| LC 1071 — Greatest Common Divisor of Strings | leetcode.com/problems/greatest-common-divisor-of-strings | Easy | GCD applied to string lengths; tests monoid intuition |
| LC 1819 — Number of Different Subsequences GCDs | leetcode.com/problems/number-of-different-subsequences-gcds | Hard | Distinct GCD values across all subsequences (not subarrays) |
| CF 474F — Ant Colony | codeforces.com/problemset/problem/474/F | Hard | GCD segment tree + counting elements equal to range GCD |
Next lesson: Extended Euclidean and Bezout's Identity — finding integers \(x, y\) such that \(ax + by = \gcd(a, b)\), and why that equation always has a solution.