Recover the Divisors
National Olympiad — National round
Submission name: guess.cpp
Problem summary
Find every positive integer D no greater than max Xi for which Xi modulo D equals Yi for every supplied pair. The observations may be inconsistent.
Input
N, then N pairs Xi Yi.
Output
First the number K of valid divisors. Then their increasing list, separated by single spaces without a trailing space; the list is empty when K=0.
Constraints
1 ≤ N ≤ 1000; 1 ≤ Xi ≤ 10^9; 0 ≤ Yi ≤ Xi.
Worked example
An independently prepared example for this explanation.
Input
2 10 2 14 2
Output
1 4
Solution analysis
- A candidate must divide every Xi−Yi and must exceed every Yi.
- Compute G=gcd(Xi−Yi), then enumerate divisors of G and retain those between max Yi+1 and max Xi.
- If G=0, every Xi equals Yi; the upper bound then makes every candidate impossible.
Why it works
The divisibility and remainder-range conditions are together equivalent to Xi mod D=Yi. Divisors of the GCD are exactly simultaneous divisors.
Watch out. A divisor of G is insufficient unless it is strictly larger than every remainder.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The divisibility and remainder-range conditions are together equivalent to Xi mod D=Yi.
// Divisors of the GCD are exactly simultaneous divisors.
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;
int main(){
int n;
cin>>n;
long long g=0,mx=0,my=0;
while(n--){
long long x,y;
cin>>x>>y;
g=gcd(g,x-y);
mx=max(mx,x);
my=max(my,y);
}
vector<long long>a;
auto put=[&](long long d){
if(d>my&&d<=mx){
a.push_back(d);
}
};
for(long long d=1;d*d<=g;d++){
if(g%d==0){
put(d);
if(d*d!=g){
put(g/d);
}
}
}
sort(a.begin(),a.end());
cout<<a.size()<<'\n';
for(int i=0;i<(int)a.size();i++){
if(i){
cout<<' ';
}
cout<<a[i];
}
cout<<'\n';
}