Sum of Floor Divisions — Solution & Editorial

Back to the Problem

Divisor-block trick: ⌊N/i⌋ is constant over maximal blocks of i; there are only O(√N) distinct values, each covering a contiguous range [i, N/(N/i)].

Complexity: O(√N)

Watch out: An O(N) loop times out at 10¹²; the block decomposition is the point. Sum reaches ~N ln N.