Editorial : Counting LCM (Hard)

From easy to hard naturally

The easy version idea is:

total pairs = $Z^2$
subtract pairs with $\mathrm{lcm}(X,Y)\le Z$

That remains correct in hard version too. The only issue is scale: $Z$ can be $10^9$, so we need stronger aggregation.

Step 1 rewrite the bad pairs

Call bad pairs:

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

Write:

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

Then:

$$ \mathrm{lcm}(X,Y)=gab. $$

So the condition $\mathrm{lcm}(X,Y)\le Z$ becomes:

$$ gab\le Z. $$

For fixed $g$, we need coprime ordered pairs $(a,b)$ with:

$$ ab\le \left\lfloor\frac{Z}{g}\right\rfloor. $$

Define:

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

Therefore:

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

And final answer:

$$ Z^2-B(Z). $$

This is the first key bridge from easy to hard.

Step 2 understand C(N) by product layers

Fix $n=ab$.

How many ordered coprime pairs $(a,b)$ satisfy $ab=n$?

$$ n=\prod p_i^{e_i}, $$

each prime power must go entirely to exactly one of $a$ or $b$ (otherwise gcd would not be 1). So each distinct prime gives 2 choices:

$$ \#(a,b)=2^{\omega(n)}. $$

Hence:

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

So now we need a fast summatory formula for $2^{\omega(n)}$.

Step 3 Mobius transform identity

Use:

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

where $\mu$ is Mobius and $\tau$ is divisor count.

Summing for $n\le N$:

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

with:

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

Now $C(N)$ is reduced to repeated queries of $D(\cdot)$.

Step 4 compute D(M) in O(sqrt M)

Since:

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

apply divisor-pair symmetry:

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

So each $D(M)$ query is $O(\sqrt M)$.

Step 5 floor-division blocking for B(Z)

We still need:

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

Values of $\lfloor Z/g\rfloor$ repeat over ranges.

For current left endpoint $l$:

$$ v=\left\lfloor\frac{Z}{l}\right\rfloor,\quad r=\left\lfloor\frac{Z}{v}\right\rfloor. $$

Then every $g\in[l,r]$ has the same quotient $v$, so contribute:

$$ (r-l+1)\cdot C(v). $$

Jump to $l=r+1$. This gives about $O(\sqrt Z)$ blocks.

Why this is still the same thought process

Easy version:

count exact-LCM distribution explicitly up to $Z$ with sieve-like loops.

Hard version:

same complement idea
same “group by arithmetic structure” habit
then stronger transforms (coprime decomposition + Mobius) to avoid linear-in-$Z$ loops.

So yes, easy version does naturally lead to hard version. You are not abandoning the idea, only compressing it.

Mapping to model_sol_2.cpp

build_mobius():

linear sieve for $\mu(d)$ up to $\sqrt{10^9}$.

divisor_count_prefix_sum(n):

computes $D(n)$ using the square-root formula.

coprime_product_pairs_prefix(n):

computes $C(n)$ from Mobius identity.
memoized to reuse repeated n values.

solve_one(z):

computes $B(Z)$ by floor-division blocks.
returns z*z - bad.

Complexity

Per test case, block count is about $O(\sqrt Z)$.

Each distinct C(v) does a sum up to $\sqrt v$, and each term calls D(v/d^2) in square-root time. The practical performance is helped by:

skipping $\mu(d)=0$
floor-block compression
memoizing C(v)

This is the intended hard-version direction for these constraints.

Practical implementation notes

Use long long everywhere (Z^2 reaches $10^{18}$ scale).
Precompute Mobius once before test loop.
Keep formulas in helper functions; the code becomes much easier to reason about than one giant loop.
Verify on easy-version samples first to build confidence.