Longest Subarray with GCD Greater Than One
National Olympiad — National round (2026 season)
Submission name: nod.cpp
Problem summary
Find the longest contiguous subarray whose GCD exceeds 1, and output its length and actual GCD. A supplied guess K differs from the correct GCD by at most 50. The longest qualifying subarray is guaranteed unique.
Input
N and the approximate GCD K, followed by N positive integers.
Output
The maximum length and the actual GCD of that subarray.
Constraints
2 ≤ N ≤ 2,000,000; 1 ≤ a[i] ≤ 1,000,000; K ≥ 2 and |K − correct GCD| ≤ 50. A unique longest qualifying subarray exists.
Worked example
An independently prepared example for this explanation.
Input
5 8 1 10 20 10 30
Output
4 10
Solution analysis
- A direct scan of every interval is too slow, and keeping all N values is unnecessary. Instead track the distinct GCDs of suffixes ending at the latest position. For each GCD, keep only the longest suffix producing it.
- For a new value x, start a one-element suffix with GCD x. Extend every previous suffix state: its new GCD is gcd(oldGCD,x) and its length increases by one.
- States are ordered from shorter to longer suffixes. Each successive GCD divides the previous one, so equal GCDs appear consecutively. Merge equal neighbors, retaining the longer length. A GCD of 1 can be discarded: adding more numbers can never increase it above 1.
- A strict decrease between positive divisors is at least a factor of two. Thus there are only O(log A) distinct suffix GCDs, where A is the largest value. The state list stays small even for two million input values.
- For 1,10,20,10,30, after 20 the states are (20,length 1) and (10,length 2). After the next 10 they merge into (10,length 3). After 30 the longest state is (10,length 4), giving 4 10.
- This streaming method solves the full problem without using the approximate K. K is still read to match the input format. Compared with checking up to 101 guessed divisors, it avoids a fixed scan of all guesses for every input value.
Why it works
Every suffix ending at a new position is either the singleton x or an old suffix extended by x, so the update represents all candidates. For equal GCDs, a longer suffix dominates a shorter one for every future extension because their future GCDs will remain equal. Discarding GCD 1 is safe. The best retained state over all ending positions is therefore the globally longest qualifying interval, and its stored GCD is exact.
Watch out. Do not treat the approximate K as exact. Do not keep only one GCD state: different suffixes can survive different future values. When merging equal GCDs keep the maximum length. Drop GCD 1, but keep the global best answer from earlier positions. This is a challenging Group E task; know Euclid’s algorithm and suffixes first.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>
using namespace std;
struct SuffixState {
int commonDivisor;
int length;
};
void addState(vector<SuffixState>& states, int commonDivisor, int length) {
if (commonDivisor <= 1) {
return;
}
if (!states.empty() && states.back().commonDivisor == commonDivisor) {
states.back().length = max(states.back().length, length);
} else {
states.push_back({commonDivisor, length});
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int count, approximateGcd;
cin >> count >> approximateGcd;
// The streaming solution does not need the approximate-GCD hint.
vector<SuffixState> previous;
vector<SuffixState> current;
previous.reserve(24);
current.reserve(24);
int bestLength = 0;
int bestGcd = 0;
for (int i = 0; i < count; i++) {
int value;
cin >> value;
current.clear();
addState(current, value, 1);
for (const SuffixState& state : previous) {
int newGcd = gcd(state.commonDivisor, value);
addState(current, newGcd, state.length + 1);
}
for (const SuffixState& state : current) {
if (state.length > bestLength) {
bestLength = state.length;
bestGcd = state.commonDivisor;
}
}
previous.swap(current);
}
cout << bestLength << ' ' << bestGcd << '\n';
}