Equal Remainders at the Border
National Olympiad — National round (2021 season)
Submission name: border.cpp
Problem summary
Given N distinct registration numbers, list every integer M > 1 for which all numbers have the same remainder on division by M.
Input
N followed by N distinct positive integers, one per line.
Output
All valid M in increasing order, separated by spaces.
Constraints
2 ≤ N ≤ 100; 1 ≤ values ≤ 1,000,000,000. At least one valid M exists.
Worked example
An independently prepared example for this explanation.
Input
3 6 34 38
Output
2 4
Solution analysis
- Two numbers have the same remainder modulo M exactly when their difference is divisible by M. Compare all values with the first value and compute the greatest common divisor G of the absolute differences.
- The answer consists of every divisor of G greater than 1. Enumerate divisors up to √G, adding each divisor and its paired quotient, then sort the list.
- For 6,34,38, the differences from 6 are 28 and 32, whose gcd is 4. Its divisors above 1 are 2 and 4. Division by 4 leaves remainder 2 for all three numbers.
Why it works
A modulus yields equal remainders exactly when it divides every difference from the first value. This is equivalent to dividing their gcd G. Divisor enumeration finds precisely those moduli; removing 1 and sorting gives the required output.
Watch out. The gcd is taken over differences, not over the original numbers. Avoid duplicating a square-root divisor. Exclude 1.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
using namespace std;
int main() {
int n, first;
cin >> n >> first;
int differenceGcd = 0;
for (int i = 1; i < n; i++) {
int value;
cin >> value;
// Equal remainders are equivalent to divisible differences.
differenceGcd = gcd(differenceGcd, abs(value - first));
}
vector<int> answer;
for (int divisor = 1; divisor <= differenceGcd / divisor; divisor++) {
if (differenceGcd % divisor == 0) {
if (divisor > 1) {
answer.push_back(divisor);
}
int other = differenceGcd / divisor;
if (other > 1 && other != divisor) {
answer.push_back(other);
}
}
}
sort(answer.begin(), answer.end());
for (int i = 0; i < static_cast<int>(answer.size()); i++) {
if (i > 0) {
cout << ' ';
}
cout << answer[i];
}
cout << '\n';
}