Lattice Points Under a Line — Solution & Editorial

Back to the Problem

The Euclidean-like 'floor_sum' recurrence computes ∑⌊(Ai+B)/C⌋ in O(log) by swapping roles of numerator and modulus, analogous to the GCD algorithm.

Complexity: O(log(max))

Watch out: An O(N) loop dies at 10⁹; the logarithmic floor-sum identity is the intended tool.