Maximum GCD of Distinct Summands
National Olympiad — Regional round (2022 season)
Submission name: parts.cpp
Problem summary
Write N as K distinct positive summands with maximum gcd.
Input
T and T pairs N K.
Output
Maximum gcd, or−1 if impossible.
Constraints
1≤T<10; 1<N<10^8; 1≤K<10^8.
Worked example
Input and output for the worked example discussed below.
Input
2 10 20 24 3
Output
-1 4
Solution analysis
- A common gcd g divides N. Dividing all summands by g leaves K distinct positive integers, whose minimum sum is S=K(K+1)/2. Thus N/g≥S.
- This condition is sufficient: use normalized1,2,…,K−1 and put the remaining sum into the last term, which is at least K. Its gcd is one because1 is present.
- Enumerate divisors of N and choose the largest g≤N/S. For24,3, g=4 gives4,8,12. For K=1, the sole summand and gcd are N.
Why it works
Every achievable gcd satisfies divisibility and the triangular minimum. The normalized construction realizes every feasible divisor with exact gcd, so the largest is optimal.
Complexity: O(√N) time and O(1) auxiliary space per case.
Watch out. Use long long for K(K+1)/2; distinctness requires more than N≥K.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
using namespace std;
// Every achievable gcd satisfies divisibility and the triangular minimum.
int main(){
int tests;
cin>>tests;
while(tests--){
long long n,k;
cin>>n>>k;
if(k==1){
cout<<n<<'\n';
continue;
}
long long minimum=k*(k+1)/2;
if(minimum>n){
cout<<-1<<'\n';
continue;
}
long long limit=n/minimum,answer=1;
for(long long d=1;d*d<=n;d++){
if(n%d){
continue;
}
if(d<=limit){
answer=max(answer,d);
}
if(n/d<=limit){
answer=max(answer,n/d);
}
}
cout<<answer<<'\n';
}
}