Coprimes
National Olympiad — Municipal round
Submission name: coprimes.cpp
Problem summary
Find the longest contiguous segment in which every pair of entries at different positions has gcd equal to 1. If no segment of length at least two exists, output 1.
Input
The number of entries, followed by the positive integers.
Output
The maximum valid segment length.
Constraints
1 ≤ N ≤ 10,000; 1 ≤ a[i] < 1000.
Worked example
An independently prepared example for this explanation.
Input
5 6 5 7 10 11
Output
3
Solution analysis
- Two numbers conflict exactly when they share a prime factor.
- For each number, extract its distinct prime factors. Repeated powers of a prime count only once.
- Keep the most recent index where each prime occurred. If that index is inside the current window, move the left end just beyond it.
- After handling all factors of the new entry, update its primes’ last positions and maximize the window length. The value 1 has no prime factors and causes no conflict.
Why it works
When a new value shares a prime with an earlier value, any valid window ending here must exclude that earlier position. Advancing left beyond all such positions gives the earliest possible valid start and thus the longest valid window ending here.
Watch out. Checking gcd only for adjacent entries is insufficient: nonadjacent entries can share a prime.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>factors(int x){
vector<int>result;
for(int p=2;p*p<=x;++p){
if(x%p==0){
result.push_back(p);
while(x%p==0){
x/=p; // Record this prime only once.
}
}
}
if(x>1){
result.push_back(x);
}
return result;
}
int main(){
int n;
cin>>n;
vector<int>last(1000,0);
int left=1,answer=1;
for(int right=1;right<=n;++right){
int x;
cin>>x;
auto primes=factors(x);
for(int p:primes){
left=max(left,last[p]+1);
}
for(int p:primes){
last[p]=right;
}
answer=max(answer,right-left+1);
}
cout<<answer<<'\n';
}