An Odd Number of Divisors
National Olympiad — Regional round (2019 season)
Submission name: odd.cpp
Problem summary
Count integers in the inclusive interval [a,b] that have an odd number of positive divisors.
Input
Two integers a and b.
Output
The count of integers with an odd divisor count.
Constraints
0 < a ≤ b < 1000000000000000.
Worked example
An independently prepared example for this explanation.
Input
4 11
Output
2
Solution analysis
- Divisors usually come in pairs d and x/d. A pair contains the same divisor twice only when d²=x. Thus exactly the perfect squares have an odd number of divisors.
- Let root(x) be the largest integer r with r²≤x. There are root(x) positive squares at most x, so subtract root(a−1) from root(b). Compute each root with integer binary search to avoid rounding near a square.
- In [4,11], the perfect squares are 4 and 9. Since root(11)=3 and root(3)=1, the answer is 3−1=2. A one-number interval contributes one exactly when that number is square.
Why it works
Pairing d with x/d accounts for every divisor. All pairs have two distinct elements except a possible square root, proving that odd divisor count is equivalent to being a square. The difference of prefix square counts includes exactly those squares in [a,b].
Complexity: O(log b) time and O(1) extra space.
Watch out. The interval endpoints are inclusive. Use integer arithmetic and include 1, which has one divisor.
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;
long long integerRoot(long long value) {
long long low = 0;
long long high = 1000000000;
while (low < high) {
long long middle = low + (high - low + 1) / 2;
if (middle * middle <= value) {
low = middle;
} else {
high = middle - 1;
}
}
return low;
}
int main() {
long long a, b;
cin >> a >> b;
// Odd divisor counts occur exactly at perfect squares.
cout << integerRoot(b) - integerRoot(a - 1) << '\n';
}