B - Triple Pair Editorial by evima
We have two solutions, so we will explain both.
1: An \(\mathrm{O}(\sqrt N)\) solution obtained by considering the maximum of \(x,y,z\) (https://atcoder.jp/contests/arc160/editorial/6381)
2: An \(\mathrm{O}(\sqrt N)\) solution obtained by considering the median of \(x,y,z\) (this page)
We assume that \(x \le y \le z\). Here, note that \(y \le \sqrt N\) from \(yz \le N\). We have the following cases. [Translator’s note: Assume that \(y\) is fixed.]
When \(x < y < z\)
The condition is equivalent to \(1 \le x < y\) and \(y < z \le \lfloor\frac{N}{y}\rfloor\). The number of such \((x, y, z)\) and their permutations is \(6(y-1) * (⌊N/y⌋ - y)\).
When \(x = y < z\)
The condition is equivalent to \(y < z \le \lfloor\frac{N}{y}\rfloor\). The number of such \((x, y, z)\) and their permutations is \(3 (\lfloor\frac{N}{y}\rfloor - y)\).
When \(x < y = z\)
The condition is equivalent to \(1 \le x < y\). The number of such \((x, y, z)\) and their permutations is \(3(y-1)\).
When \(x=y=z\)
Only one \((x, y, z)\) satisfies the condition.
Therefore, you should take the sum for all \(y\) of the above four patterns. The time complexity is \(\mathrm{O}(\sqrt N)\) per case, which is sufficiently fast.
posted:
last update: