Divide and Conquer the GCD
Autumn Tournament (2021)
Submission name: divide.cpp
Problem summary
For each pair (a,b), repeatedly move a divisor from either number to the other: (a,b) may become (a/d,b·d) when d divides a, or (a·d,b/d) when d divides b. Find the largest gcd achievable.
Input
N and Q, then Q positive pairs a,b.
Output
Q answers on one line, in input order.
Constraints
1 ≤ N ≤ 2000000; 1 ≤ Q ≤ 500000; 1 ≤ a,b ≤ N.
Worked example
Original statement sample.
Input
100 3 2 8 6 72 38 39
Output
4 12 1
Solution analysis
- Every move preserves the product P=a·b. For each prime p with total exponent e in P, a common divisor can contain at most floor(e/2) copies of p. We can attain this by splitting the exponent as evenly as possible between the two numbers; prime factors can be transferred individually. The answer is the square root of the largest square dividing P.
- For fast queries, preprocess a smallest-prime-factor sieve up to N. Also write each value v as squareRoot[v]² × squareFree[v], where squareFree has no repeated prime factor. With p=spf[v] and q=v/p: if p divides q, remove p² and multiply squareRoot[v/p²] by p; otherwise copy squareRoot[q] and multiply squareFree[q] by p.
- Then the answer is squareRoot[a] × squareRoot[b] × gcd(squareFree[a],squareFree[b]). Square factors already inside a or b are handled by the first two factors; a prime appearing once in both square-free kernels contributes one additional shared factor. Each query needs only one gcd.
- For (6,72), 6=1²·6 and 72=6²·2, giving 1·6·gcd(6,2)=12. One reachable pair is (36,12), whose gcd is 12. For (38,39), the product is square-free, so the answer is 1.
Why it works
The product invariant bounds every common prime exponent by floor(e/2). Transferring prime divisors allows that exponent balance for every prime independently, achieving the bound. The square-root/kernel formula computes precisely these exponents, so it gives the maximum attainable gcd.
Watch out. Do not maximize gcd only among the original divisors of gcd(a,b): factors can move between numbers. The N bound applies to input values, not intermediate values. Use long long in the answer multiplication.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<numeric>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int limit,queries;
cin>>limit>>queries;
vector<int>smallest(limit+1,0);
for(int prime=2;prime<=limit;prime++){
if(smallest[prime]!=0){
continue;
}
smallest[prime]=prime;
if(1LL*prime*prime<=limit){
for(int value=prime*prime;value<=limit;value+=prime){
if(smallest[value]==0){
smallest[value]=prime;
}
}
}
}
vector<int>squareRoot(limit+1,1),squareFree(limit+1,1);
for(int value=2;value<=limit;value++){
int prime=smallest[value];
int quotient=value/prime;
if(quotient%prime==0){
// Pull one complete prime square out of the value.
squareRoot[value]=squareRoot[quotient/prime]*prime;
squareFree[value]=squareFree[quotient/prime];
}
else{
squareRoot[value]=squareRoot[quotient];
squareFree[value]=squareFree[quotient]*prime;
}
}
for(int query=0;query<queries;query++){
int a,b;
cin>>a>>b;
long long answer=1LL*squareRoot[a]*squareRoot[b]*gcd(squareFree[a],squareFree[b]);
if(query>0){
cout<<' ';
}
cout<<answer;
}
cout<<'\n';
}