Hints: Counting LCM (Easy)

Start from the quantity you are asked to count:

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

Counting this directly is awkward. Can you instead count the opposite condition first?

Total ordered pairs is just:

$$ Z^2 $$

So if you can compute:

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

then the answer is:

$$ Z^2 - \text{that count}. $$

How can $\mathrm{lcm}(X,Y) \le Z$ be counted?

Group pairs by their exact LCM value $L$.

If you know, for every $L \le Z$, how many ordered pairs satisfy $\mathrm{lcm}(X,Y)=L$, then summing those values over $L=1..Z$ gives the full count of “bad” pairs.

Fix a value $L$. First count pairs where both numbers divide $L$:

• Number of divisors of $L$ is $d(L)$.
• So number of ordered pairs $(a,b)$ with $a \mid L$ and $b \mid L$ is $d(L)^2$.

This counts pairs with LCM equal to $L$, but also pairs whose LCM is a proper divisor of $L$.

Let:

$$ f(L) = \#\{(a,b): \mathrm{lcm}(a,b)=L\}. $$

From the previous hint:

$$ d(L)^2 = \sum_{t \mid L} f(t). $$

This is a divisor-sum relation. You can recover $f(L)$ by removing contributions of smaller divisors.

One practical way:

1. Initialize f[L] = d(L)^2.
2. For every divisor d, subtract f[d] from all multiples 2d, 3d, ....

After processing all d in increasing order, each f[L] becomes the number of pairs with exact LCM L.

Now the bad-pair count is:

$$ \sum_{L=1}^{Z} f(L). $$

And final answer per test case:

$$ Z^2 - \sum_{L=1}^{Z} f(L). $$

This exactly matches the structure in model_sol.cpp.

Complexity target with constraints:

• Need all test cases together in roughly $O\!\left(\sum Z \log Z\right)$ scale.
• Nested loops of the form for d in [1..Z], for multiple in [d, 2d, ...] are harmonic and fast enough for this easy version.

If you are optimizing further, think about precomputing once up to max $Z$ across all test cases.