Largest Common Prime Divisor in a Window
Autumn Tournament (2023)
Submission name: gcdp.cpp
Problem summary
For each contiguous length-k window, find its largest common prime divisor, or use 1 when no prime divides every element. Output the maximum of these values over all windows. Here 1 is a fallback, not a prime number.
Input
n k, followed by n positive values.
Output
The maximum window answer.
Constraints
2 ≤ k ≤ n ≤ 1000000; every value ≤ 1000000.
Worked example
Original statement sample.
Input
7 3 18 6 12 20 30 20 7
Output
5
Solution analysis
- A prime divides every value in a window exactly when it divides their gcd. Thus first obtain each window gcd, then its largest prime factor. Precompute largestPrime[x] for all x up to the maximum array value by a sieve, overwriting multiples as primes increase. Set largestPrime[1]=1.
- Partition the array into blocks of length k. Compute prefix gcds from each block start and suffix gcds toward each block end. Any length-k window crosses at most two blocks: gcd(suffix[left],prefix[right]) is its gcd. If it is one complete block, the duplicated coverage does not matter because gcd(x,x)=x.
- For the sample the five window gcds are 6,2,2,10,1. Their largest prime factors are 3,2,2,5,1; the maximum is 5. The block arrays avoid rescanning k values for every window.
Why it works
Associativity of gcd lets the two block fragments combine into precisely the window gcd. A prime is common to the window iff it divides that gcd. The sieve visits all multiples of each prime in increasing prime order, leaving the largest factor; maximizing these values gives the required result.
Watch out. Do not output the largest gcd itself: gcd 12 has largest prime factor 3. A final short block must end its suffix at n−1. Initialize value 1 separately.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Associativity of gcd lets the two block fragments combine into precisely the window gcd. A
// prime is common to the window iff it divides that gcd.
#include<algorithm>
#include<iostream>
#include<numeric>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,length;
cin>>n>>length;
vector<int>values(n);
int maximum=1;
for(int&value:values){
cin>>value;
maximum=max(maximum,value);
}
vector<int>largestPrime(maximum+1,0);
largestPrime[1]=1;
for(int prime=2;prime<=maximum;prime++){
if(largestPrime[prime]==0){
for(int multiple=prime;multiple<=maximum;multiple+=prime){
largestPrime[multiple]=prime;
}
}
}
vector<int>prefix(n);
vector<int>suffix(n);
for(int i=0;i<n;i++){
prefix[i]=i%length==0?values[i]:gcd(prefix[i-1],values[i]);
}
for(int i=n-1;i>=0;i--){
bool blockEnd=i==n-1||(i+1)%length==0;
suffix[i]=blockEnd?values[i]:gcd(suffix[i+1],values[i]);
}
int answer=1;
for(int left=0;left+length<=n;left++){
int windowGcd=gcd(suffix[left],prefix[left+length-1]);
answer=max(answer,largestPrime[windowGcd]);
}
cout<<answer<<'\n';
}