Least and Most Trivial
National Olympiad — National round (2018 season)
Submission name: trivial.cpp
Problem summary
The triviality of a positive integer x is the sum of its proper positive divisors divided by x. In the inclusive interval [a,b], find the integer with minimum triviality and the integer with maximum triviality. For each tie, choose the smallest integer.
Input
Two integers a and b.
Output
The minimum-triviality integer and maximum-triviality integer, separated by a space.
Constraints
1 ≤ a < b ≤ 10000.
Worked example
An independently prepared example for this explanation.
Input
24 28
Output
25 24
Solution analysis
- First compute proper-divisor sums for every value up to b. For each divisor d, add d to its multiples 2d,3d,…; starting at 2d excludes the number itself.
- Compare two ratios sum[x]/x exactly by cross multiplication: compare sum[x]·y with sum[y]·x. Scan the interval in increasing order and replace a winner only on a strict improvement, preserving the smallest value on ties.
- For [24,28], 25 has proper divisors 1 and 5, giving 6/25. The value 24 has divisor sum 36, giving 36/24. These are respectively the minimum and maximum in this interval.
Why it works
The sieve adds d to x exactly when d is a proper divisor of x, so all numerator sums are exact. Since denominators are positive, cross multiplication preserves the order of their ratios. Strict updates during an increasing scan retain the first integer attaining each optimum.
Watch out. The number 1 has proper-divisor sum zero. Avoid floating-point equality tests; wide integer products make exact comparisons easy.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
vector<long long> sum(b + 1, 0);
for (int divisor = 1; divisor <= b / 2; ++divisor) {
for (int multiple = 2 * divisor; multiple <= b; multiple += divisor) {
sum[multiple] += divisor;
}
}
int least = a;
int greatest = a;
for (int value = a + 1; value <= b; ++value) {
// Cross multiplication compares rational trivialities exactly.
if (sum[value] * least < sum[least] * value) {
least = value;
}
if (sum[value] * greatest > sum[greatest] * value) {
greatest = value;
}
}
cout << least << ' ' << greatest << '\n';
}