Crimson Triples

The scary expression is mostly cosplay. The actual condition is just divisibility.

For each prime $p$, write $x=v_p(a)$, $y=v_p(b)$, and $z=v_p(c)$. The condition becomes

$$\min(\max(x,y),\max(y,z))=\min(x,z).$$

Using

$$\min(\max(x,y),\max(z,y))=\max(y,\min(x,z)),$$

the left side becomes $\max(y,\min(x,z))$. This equals $\min(x,z)$ exactly when

$$y\le \min(x,z).$$

So for every prime $p$,

$$v_p(b)\le \min(v_p(a),v_p(c)).$$

That means $b$ divides both $a$ and $c$. Equivalently, $b\mid \gcd(a,c)$.

Now counting is easy. Fix $b$. The number of choices for $a$ is the number of multiples of $b$ from $1$ to $n$:

$$\left\lfloor \frac{n}{b}\right\rfloor.$$

Same for $c$, independently. So fixed $b$ contributes

$$\left\lfloor \frac{n}{b}\right\rfloor^2$$

valid triples.

Therefore the answer is

$$\sum_{b=1}^{n}\left\lfloor \frac{n}{b}\right\rfloor^2.$$

Since the total sum of $n$ over all tests is at most $2\cdot 10^5$, a direct loop over $b=1\ldots n$ per test case is completely fine.

Time complexity: $O(\sum n)$.

Memory complexity: $O(1)$.