Note that for the tuples \((a, b, c)\) we wish to count, if \(a < b\), \(a = c\), therefore we can rule out those. This leaves \(\binom N 2 = N(N-1) / 2\) possible tuples where \(a > b\), with the only exceptions being where \(c = 0\), therefore we must filter out the tuples where \(b\) divides \(a\).

If we fix \(b\), there are \(\lfloor N/b \rfloor -1\) tuples where \(b\) divides \(a\) to subtract. To do this efficiently, we want to enumerate through triples \((l, r, q)\) such that:

• For all integers \(l \le b < r\) [note the half-open range], \(q = \lfloor N/b \rfloor\)
• All \(q\) are distinct, and segments \([l, r)\) would cover the range \([1, N]\) without overlapping.

We claim that there are at most \(O(\sqrt N)\) such triples. Proof: there are at most \(\sqrt N\) possible triples where \(q \le \sqrt N\). If \(q > \sqrt N\), \(l < \sqrt N\), therefore there are again at most \(\sqrt N\) triples.

We can enumerate through these triples via the following algorithm:

• Start with \(l := 1\).
• While \(l \le n\):
  • \(q := \lfloor N/l \rfloor\)
  • \(r := \lfloor N/q \rfloor + 1\)
  • yield \((l, r, q)\)
  • reassign \(l := r\)

This is a variant of a common technique of enumerating floored quotients of \(N\) in \(O(\sqrt N)\) time (link to yosupo.jp library checker)

For each \((l, r, q)\) triple, we can thus subtract \((r - l)(q - 1)\) from the answer.