1411. Add Up floor(n/i) for Every i
For each query print the sum of floor(n/i) for i from 1 to n. Print 0
when n is 0.
n = 1 -> 1
n = 2 -> 2 + 1 = 3
n = 10 -> 10 + 5 + 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 = 27
## What most people try first
Loop i from 1 to n. With n at 10^12 and up to 100 queries that is
10^14 divisions, which no time limit permits. There is nothing wrong with the
formula, only with the number of terms.
## The quotient takes very few distinct values
floor(n/i) is constant on long runs of i. The run containing a given i
ends at exactly
last = n / (n / i)
using integer division both times. So the sum can be walked block by block,
each block contributing (n/i) * (last - i + 1):
i = 1
while i <= n:
v = n / i
last = n / v
total += v * (last - i + 1)
i = last + 1
There are at most 2 * sqrt(n) blocks, because every i at or below
sqrt(n) can start its own block while every quotient above sqrt(n)
corresponds to an i below sqrt(n). For n = 10^12 that is two million
steps, not 10^12.
## Why the block end is right
Let v = floor(n/i). For any j, floor(n/j) = v holds exactly when
v <= n/j < v + 1, that is n/(v+1) < j <= n/v. The largest integer j
satisfying the right-hand side is floor(n/v), which is the formula above.
Because v was computed from i, we already know i satisfies the
inequality, so the run starting at i really does end at floor(n/v) and the
next block starts one past it. Nothing is skipped and nothing is counted
twice.
## What the sum means
This quantity is also the total number of divisors of all the integers from 1
to n, because floor(n/i) counts the multiples of i in that range, and a
pair (i, m) with i dividing m is counted once from each side. That is the
second identity the oracle uses to check the answers: the sum equals
2 * (floor(n/1) + ... + floor(n/r)) - r^2 with r = floor(sqrt(n)), which
comes from counting the lattice points under the hyperbola x * y = n by
symmetry. Problem 1341 computes the divisor counts individually with a sieve,
which is a different tool for a different size of n.
## Overflow
n reaches 10^12, which needs 64 bits: a signed 32-bit integer stops at
2147483647, and a 32-bit build answers 0 where the truth is 27785452448917.
The answer is about n * (ln n + 2*0.5772 - 1), near 2.8 * 10^13, so it also
needs 64 bits and the product v * (last - i + 1) is at most n itself. In
JavaScript, and this is the unusual part, BigInt is not needed: 10^12 and
2.8 * 10^13 are both well below 2^53. What is needed is an exact floor,
because Math.floor(n / v) is a double division; the reference follows it
with an integer correction step, whose own products stay near 2 * 10^12 and
so remain exact.
## Cost
O(sqrt(n)) per query.
Constraints - `1 ≤ q ≤ 100` - `0 ≤ n ≤ 1000000000000`
Input
The first line contains q.
The next q integers are the values n, and may be laid out one per line or
several to a line.
Output
For each query print the sum, one per line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.