PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Square root decomposition
PROBLEM:
Given N, count pairs (X, Y) such that 1 \le X \lt Y \le N and \gcd(X, Y) = |X-Y|.
EXPLANATION:
Let’s fix g = \gcd(X, Y) and try to count pairs with |X-Y| = \gcd(X, Y) = g.
\gcd(X, Y) = g means that X and Y must both be multiples of g.
So, let’s write X = ag and Y = bg.
Since we want X \lt Y, we have |X-Y| = Y-X, so that Y = X+g.
Thus, bg = ag + g = g\cdot (a+1), which gives b = a+1.
So, after fixing g, fixing either a or b automatically fixes the other one too.
We want 1 \le X, Y \le N, which means 1 \le a, b \le \frac{N}{g}.
Since a, b must be integers, a stricter bound on them is \text{floor}\left(\frac{N}{g}\right), which will be denoted \left\lfloor \frac{N}{g} \right\rfloor.
Now, b cannot be equal to 1, since then a would become 0.
However, any other value is fine for b to take.
Thus, after fixing g, there are \left\lfloor \frac{N}{g} \right\rfloor - 1 possible values b can take; for each of which a becomes determined uniquely hence giving us one pair of (X, Y).
Thus, summing up across all g from 1 to N (since the gcd cannot exceed N), the answer is
However, N can be as large as 10^9, so we need a faster algorithm to compute this.
We’ll use square-root decomposition, by treating g \le \sqrt N and g \gt \sqrt N separately.
This is because, for g \gt \sqrt N, the value of \left\lfloor \frac{N}{g} \right\rfloor will be \le \sqrt N, and thus across all those values of g there are only \sqrt N distinct values it can take.
So, first for each g \le \sqrt N, add \left\lfloor \frac{N}{g} \right\rfloor - 1 to the answer.
We now need to solve for g \gt \sqrt N.
Let’s fix a value k \le \sqrt N, and try to count how many g \gt \sqrt N satisfy k = \left\lfloor \frac{N}{g} \right\rfloor.
There are a couple of ways to find this count.
The “brainless” method is to simply binary search: find the smallest integer g_1 with k \ge \left\lfloor \frac{N}{g_1} \right\rfloor and the largest integer g_2 with k \le \left\lfloor \frac{N}{g_2} \right\rfloor, and then the count is simply all integers in the range [g_1, g_2].
This works because the function \left\lfloor \frac{N}{g} \right\rfloor is non-increasing as g increases.
Alternately, you can skip the binary search and just use a bit of math.
The largest allowed integer must satisfy g_2 \le \frac{N}{k}, so naturally that gives g_2 = \left\lfloor \frac{N}{k} \right\rfloor.
Similarly, the smallest value will be g_1 = \left\lfloor \frac{N}{k+1} \right\rfloor + 1, because anything smaller will have k+1 multiples at least.
Once g_1 and g_2 are known, simply add (g_2 - g_1 + 1) \cdot (k-1) to the answer.
Do this for each 1 \le k \le \sqrt N and we’re done!
Note that you’ll have to be careful with k around \sqrt N, so as to not count it in both parts.
TIME COMPLEXITY:
\mathcal{O}(\sqrt N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
ans = -n
for i in range(1, n+1):
if i*i > n: break
ans += n//i
if i != n//i: ans += i*(n//i - n//(i+1))
print(ans)