Editorial : Counting LCM (Easy)

We need ordered pairs $(X, Y)$ with:

• $1 \le X, Y \le Z$
• $\mathrm{lcm}(X, Y) > Z$

Directly handling “$> Z$” is uncomfortable. A smoother route is:

1. count all pairs: $Z^2$
2. subtract pairs with $\mathrm{lcm}(X, Y) \le Z$

So define:

Then:

The full task becomes: how do we compute $B(Z)$ quickly?

Instead of checking every pair, group by exact LCM value.

Let:

Then:

So we only need all $f(1), f(2), \dots, f(Z)$.

Fix some $L$.

How many ordered pairs $(a,b)$ satisfy $a \mid L$ and $b \mid L$?

If $d(L)$ is the number of divisors of $L$, this is:

But that includes all pairs whose LCM is any divisor of $L$, not just exactly $L$.

So:

This is the key divisor relation.

The relation says every $f(t)$ contributes to all multiples of $t$.

One intuitive inversion strategy:

• start with f[L] = d(L)^2
• remove smaller exact-LCM contributions from larger multiples

In code terms:

1. Build divisors[x] = d(x) for all $x \le Z$.
2. Set f[x] = divisors[x] * divisors[x].
3. For each d from 1 to Z, subtract f[d] from f[2d], f[3d], ....

After this sieve-like subtraction, f[L] becomes exactly the count of ordered pairs with LCM equal to $L$.

This is exactly what your count_lcm_pairs() does.

When we initialize f[L] = d(L)^2, each f[L] holds:

Processing divisors in increasing order means when we stand at d, f[d] is already exact. Subtracting it from all proper multiples removes its “shadow” there.

By the time we finish, every f[L] has had all proper-divisor contributions removed, so only exact-LCM count remains.

From model_sol.cpp:

• divisors[multiple]++ over multiples computes $d(x)$ for each $x$.
• ans[i] = divisors[i] * divisors[i] initializes $d(i)^2$.
• nested subtraction over multiples performs the inversion.
• sum = accumulate(ans.begin(), ans.end(), 0LL) gives $B(Z)$.
• output is z*z - sum.

So the implementation follows the exact mathematical path above.

For one test with value $Z$:

• divisor counting loop: $O(Z \log Z)$ harmonic complexity
• subtraction loop: also $O(Z \log Z)$

Total:

With constraint $\sum Z \le 10^6$, this is fast enough.

A practical pattern to remember:

1. Complement count if direct condition is hard.
2. Group objects by an exact arithmetic value (here exact LCM).
3. Find an easier “overcount by divisibility” quantity.
4. Remove divisor contributions using a multiples loop.

This pattern appears often with gcd/lcm, divisor sums, and multiplicative-style counting problems.