Hints: Counting LCM (Hard)

Start exactly like the easy version.

You want:

$$ \#\{(X,Y): 1 \le X,Y \le Z,\ \mathrm{lcm}(X,Y) > Z\}. $$

Count complement first:

$$ \text{answer} = Z^2 - \#\{(X,Y): \mathrm{lcm}(X,Y)\le Z\}. $$

The easy version grouped by exact LCM value.

That still works conceptually, but now $Z$ can be up to $10^9$, so any $O(Z)$ or even $O(Z \log Z)$ per test is too slow.

So keep the same math direction, but search for a way to aggregate many values at once.

Try changing variables:

Let

$$ X = g a,\quad Y = g b,\quad \gcd(a,b)=1. $$

Then

$$ \mathrm{lcm}(X,Y)=g a b. $$

So bad pairs ($\mathrm{lcm}\le Z$) are counted by:

$$ \sum_{g=1}^{Z} \#\{(a,b): \gcd(a,b)=1,\ ab \le \lfloor Z/g \rfloor\}. $$

Define:

$$ C(N)=\#\{(a,b): \gcd(a,b)=1,\ ab\le N\}. $$

Then:

$$ \text{bad}=\sum_{g=1}^{Z} C\!\left(\left\lfloor \frac{Z}{g}\right\rfloor\right). $$

Now the whole problem is reduced to evaluating $C(N)$ quickly and then summing it with floor-division blocks.

How to understand $C(N)$?

If you fix product $n = ab$, then the number of ordered coprime factor pairs $(a,b)$ with $ab=n$ is:

$$ 2^{\omega(n)}, $$

where $\omega(n)$ is number of distinct prime factors.

So:

$$ C(N)=\sum_{n\le N}2^{\omega(n)}. $$

Useful identity:

$$ 2^{\omega(n)}=\sum_{d^2\mid n}\mu(d)\,\tau\!\left(\frac{n}{d^2}\right), $$

with $\mu$ = Mobius, $\tau$ = divisor-count function.

After summing $n \le N$ and swapping order:

$$ C(N)=\sum_{d\le \sqrt N}\mu(d)\,D\!\left(\left\lfloor\frac{N}{d^2}\right\rfloor\right), $$

where

$$ D(M)=\sum_{k\le M}\tau(k). $$

Now focus on computing $D(M)$ in $O(\sqrt M)$:

$$ D(M)=\sum_{i=1}^{M}\left\lfloor\frac{M}{i}\right\rfloor. $$

By symmetry of divisor pairs:

$$ D(M)=2\sum_{i=1}^{\lfloor\sqrt M\rfloor}\left\lfloor\frac{M}{i}\right\rfloor-\lfloor\sqrt M\rfloor^2. $$

So one evaluation of $C(N)$ is:

• loop $d=1..\lfloor\sqrt N\rfloor$
• skip if $\mu(d)=0$
• add $\mu(d)\cdot D(\lfloor N/d^2\rfloor)$

You can precompute $\mu$ once up to $\sqrt{10^9}$ by linear sieve.

Final sum:

$$ \sum_{g=1}^{Z}C\!\left(\left\lfloor\frac{Z}{g}\right\rfloor\right) $$

has many repeated values of $\lfloor Z/g\rfloor$.

Use floor-division block trick:

• for current l, let v = Z/l
• all g in [l, r] with r = Z/v share same value v
• add (r-l+1) * C(v)
• jump l = r+1

If you want a practical speed boost, memoize computed C(v) values in a hash map, because block values repeat across test cases too.

Put it all together:

1. Precompute $\mu$ up to $31623$.
2. For each test case:
   • compute bad by floor-division blocks and C(v).
   • answer is Z*Z - bad.

This is the hard-version extension of easy-version logic, not a totally new idea.