Pairs and Divisor Counts
National Olympiad — National round (2023 season)
Submission name: divs.cpp
Problem summary
Let d(x) be the number of positive divisors of x. Count pairs 1≤x≤y≤N satisfying K·d(x)·d(y)=x·y.
Input
N K.
Output
The number of qualifying pairs.
Constraints
1 ≤ N ≤ 40000; 1 ≤ K ≤ 10^9.
Worked example
An independently prepared example for this explanation.
Input
8 3
Output
2
Solution analysis
- Compute all divisor counts with a sieve: every divisor d contributes one to d,2d,3d,… . The equation can then be written x/d(x)=K·d(y)/y.
- Represent every rational number by its numerator and denominator divided by their gcd. Scan y upward, insert the ratio y/d(y) into a frequency map, then query the reduced ratio K·d(y)/y. Inserting first permits x=y; earlier inserted values ensure x≤y.
- For N=8,K=3, y=8 has d(8)=4 and needs x/d(x)=12/8=3/2. Both x=3 and x=6 have this ratio, giving the two sample pairs. Exact fractions avoid floating-point equality errors.
Why it works
The sieve counts each divisor once. For each y, the map contains exactly the ratios of x≤y, and the algebraic rearrangement is equivalent to the original equation. The matching frequency therefore counts exactly the valid pairs with that second coordinate, without duplication.
Watch out. Include diagonal pairs by inserting before querying. Reduce both fractions. Use long long for K·d(y), the answer, and fraction components.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <utility>
using namespace std;
int main() {
int n;
long long k;
cin >> n >> k;
vector<int> divisors(n + 1, 0);
for (int divisor = 1; divisor <= n; divisor++) {
for (int multiple = divisor; multiple <= n; multiple += divisor) {
divisors[multiple]++;
}
}
map<pair<long long, long long>, long long> frequency;
long long answer = 0;
for (long long y = 1; y <= n; y++) {
long long common = gcd(y, static_cast<long long>(divisors[y]));
frequency[{y / common, divisors[y] / common}]++;
// Query the exact reduced ratio K*d(y)/y among already inserted x.
long long numerator = k * divisors[y];
common = gcd(numerator, y);
auto found = frequency.find({numerator / common, y / common});
if (found != frequency.end()) {
answer += found->second;
}
}
cout << answer << '\n';
}