Count Special Divisors
National Olympiad — Regional round (2024 season)
Submission name: divisor.cpp
Problem summary
A special divisor of n is an integer d with 1<d<n such that integer quotient n/d equals remainder n%d. Count all such pairs (n,d) with A≤n≤B.
Input
A B.
Output
The sum of the special-divisor counts over the inclusive interval.
Constraints
1 < A ≤ B < 500000.
Worked example
An independently prepared example for this explanation.
Input
15 17
Output
5
Solution analysis
- Write the common quotient and remainder as q. Then n=q·d+q=q(d+1), and a valid remainder requires 1≤q<d. Conversely, any such q,d produce a special divisor.
- For fixed q, n lies in [A,B] exactly when ceil(A/q)−1≤d≤floor(B/q)−1. Intersect this interval with d≥max(2,q+1), then add its integer length. No actual numbers or divisors need to be stored.
- The smallest possible n for q is q(q+2), so stop when this exceeds B. In 15…17, q=1 gives d=14,15,16; q=2 gives d=7 for n=16; q=3 gives d=4 for n=15, for five pairs.
Why it works
The quotient-remainder identity establishes a bijection between special-divisor pairs and integer choices q,d with n=q(d+1), q<d and d>1. For each feasible q the bounds count exactly these d, and the stopping bound excludes all remaining q.
Watch out. A special divisor need not divide n evenly. The quotient is positive and strictly smaller than d. Use inclusive interval counts.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
long long a, b;
cin >> a >> b;
long long answer = 0;
for (long long quotient = 1; quotient * (quotient + 2) <= b; quotient++) {
// n=q*(d+1), with d>q and d>1, turns the search into interval counting.
long long low = max(2LL, max(quotient + 1, (a + quotient - 1) / quotient - 1));
long long high = b / quotient - 1;
if (low <= high) {
answer += high - low + 1;
}
}
cout << answer << '\n';
}