PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Ildar Gainullin
Tester: Nikolay Budin
Editorialist: Alei Reyes
DIFFICULTY:
Easy
PREREQUISITES:
Divisibility
PROBLEM:
A fraction \frac{a}{b} is good if it is equal to \frac{c}{c+1} for some positive integer c.
You are given one integer n. Find the number of pairs of integers a, b (1 \leq a, b \leq n), such that the fraction f(a,b)=\frac{a}{a + 1} \cdot \frac{b+1}{b} is good.
QUICK EXPLANATION
We are looking for pairs where f(a,b)=c/(c+1), for some integer c. Express c in terms of a and b, then simplify the numerator by taking the gcd with the denominator. It turns out that we only have to look for the divisors of a and a+1.
EXPLANATION:
In number theory problems, sometimes is useful to play with small values and try to discover some properties, you can even write a program that runs over all small values of (a,b) and spot some patterns. I wrote small fractions of the form a/(a+1) and its multiples a \cdot k / (a+1) \cdot k, then I simplified the resulting f(a,b), and after making some conjectures about the behaviour of f(a,b), I performed the following algebraic analysis.
A good fraction is always smaller than 1, therefore \frac{a}{a+1} \cdot \frac {b+1}{b} \lt 1, after simplifying we get that a \lt b.
We are interested in pairs (a, b) such that there exists an integer c where \frac{a}{a+1} \cdot \frac{b+1}{b} = \frac{c}{c+1}. Let’s isolate the term c in function of a and b:
Since a \lt b, we can write b=a+d, for some positive integer d. The expression for c now becomes:
Let’s simplify common factors between each member of the numerator with the denominator:
- We can simplify at most x=gcd(a,d) from the first term.
- We can simplify at most y=gcd(a+d+1,d) from the second term. By the euclidean algorithm we know that gcd(a,b)=gcd(b,a-b), therefore y=gcd(a+1,d).
That means that to make c an integer, we can set d = x' \cdot y', where x' is any divisor of a, and y' any divisor of a+1. Since a and a+1 are coprime, they don’t have common divisors, and we’ll always get different values for d.
Let’s brute force all integers a from 1 to n, iterate over each divisors x' of a and count the valid values of y'. Note that b \leq n, therefore a + x' \cdot y' \leq n, that means we have to count only the y' \leq (n-a)/x'. If we store the divisors of each integer in increasing order in a vector, we can count all such y' with binary search, or two pointers.
SOLUTIONS:
Setter's Solution
const int N = 1e6 + 20;
int d[N];
int main() {
for (int i = 1; i < N; i++) {
for (int j = i; j < N; j += i) {
d[j]++;
}
}
int n;
cin >> n;
ll ans = 0;
for (int i = 1; i <= n; i++) {
ans += d[i] * (ll) d[i + 1] / 2 - 1;
}
cout << ans << '\n';
}
Tester's Solution
void solve() {
int n;
cin >> n;
vector<int> sieve(n + 2);
for (int i = 2; i <= n; ++i) {
if (!sieve[i]) {
for (int j = i; j <= n; j += i) {
sieve[j] = i;
}
}
}
ll ans = 0;
gp_hash_table<int, int> cnt;
auto find_divs = [&](vector<int>& divs, int num) {
divs.clear();
cnt.clear();
while (num > 1) {
cnt[sieve[num]]++;
num /= sieve[num];
}
divs.push_back(1);
for (pii p : cnt) {
int sz = szof(divs);
for (int q = 0; q < sz * p.ss; ++q) {
divs.push_back(divs[q] * p.ff);
}
}
sort(divs.begin(), divs.end());
};
vector<int> cur_divs = {1};
vector<int> next_divs = {1, 2};
for (int i = 1; i < n; ++i) {
int c = szof(next_divs);
for (int q = 0; q < szof(cur_divs); ++q) {
while (c > 0 && i + (ll) next_divs[c - 1] * cur_divs[q] > n) {
--c;
}
ans += c;
}
if (i < n - 1) {
swap(next_divs, cur_divs);
find_divs(next_divs, i + 2);
}
}
cout << ans << "\n";
}