Number-Theoretic Block Decomposition

$|D(n)|\le 2\sqrt{n}$.

Consider two cases:

• When $i\le\sqrt{n}$, there are at most $i$ possible values of $\sqrt{n}$, so there are also at most $\left\lfloor\dfrac{n}{i}\right\rfloor$ possible values of $\sqrt{n}$.
• When $i>\sqrt{n}$, $\left\lfloor\dfrac{n}{i}\right\rfloor \le\dfrac{n}{i} < \sqrt{n}$, so there are again at most $\sqrt{n}$ possible values.

Therefore, the total number of possible values is $|D(n)|\le 2\sqrt{n}$.

Let $s = \lfloor\sqrt{n}\rfloor$. The elements of $D(n)$ in increasing order are

Consequently, $|D(n)| = \lfloor \sqrt{4n+1}\rfloor - 1$.

First, for $1 \le i \le s$, one can prove that $\left\lfloor\dfrac{n}{\lfloor n/i\rfloor}\right\rfloor = i$. Let $d = \left\lfloor\dfrac{n}{i}\right\rfloor$; we need to prove $\left\lfloor\dfrac{n}{d}\right\rfloor = i$. Written as inequalities, this means that given $d \le \dfrac{n}{i} < d + 1$, we need to prove $i \le \dfrac{n}{d} < i + 1$. The given condition can be written as $i\le\dfrac{n}{d} < i + \dfrac{i}{d}$, so it is enough to prove $\dfrac{i}{d} \le 1$, that is, $i \le d = \left\lfloor\dfrac{n}{i}\right\rfloor$. This is equivalent to $i \le \dfrac{n}{i}$, which holds for every $1 \le i \le s \le \sqrt{n}$.

This result actually shows that the mapping $i \mapsto \left\lfloor\dfrac{n}{i}\right\rfloor$ is a bijection between $\{i:1\le i \le s\}$ and $\left\{\left\lfloor\dfrac{n}{i}\right\rfloor: 1\le i\le s\right\}$. Since the values of $i$ are distinct, the values of $\left\lfloor\dfrac{n}{i}\right\rfloor$ are also distinct. The only possible common elements of the two sets are $s$ and $\left\lfloor\dfrac{n}{s}\right\rfloor$. Therefore, $|D(n)|=2s - \left[s = \lfloor n/s\rfloor\right]$.

To obtain the final expression for $|D(n)|$, we need to determine when $s = \left\lfloor\dfrac{n}{s}\right\rfloor$ holds.

• When $s = \left\lfloor\dfrac{n}{s}\right\rfloor$, we always have $s \le \dfrac{n}{s} < s + 1$, that is, $s^2 \le n < s^2+s$. Thus, $4s^2 + 1 \le 4n + 1 < 4s^2+4s+1 = (2s+1)^2$. Since $4n+1$ is always odd, the left side can equivalently be relaxed to $4s^2$, so this condition is equivalent to $2s \le \sqrt{4n+1} < 2s+1$, that is, $\lfloor \sqrt{4n+1}\rfloor = 2s$.
• When $s < \left\lfloor\dfrac{n}{s}\right\rfloor$, we always have $s + 1 \le \dfrac{n}{s}$, that is, $s^2 + s\le n$. Since $n < (s+1)^2$, we have $s^2 + s\le n < (s+1)^2$. This is equivalent to $(2s+1)^2\le 4n+1 < 4(s+1)^2+1$. Again using the fact that $4n+1$ is odd, the right side can equivalently be tightened to $4(s+1)^2$, so this condition is equivalent to $2s+1\le\sqrt{4n+1} < 2s+2$, that is, $\lfloor \sqrt{4n+1}\rfloor = 2s+1$.

Summarizing these two cases gives $|D(n)| = \lfloor \sqrt{4n+1}\rfloor - 1$.

For $d\in D(n)$, the range of integer values of $\left\lfloor\dfrac{n}{i}\right\rfloor=d$ satisfying $i$ is

Since $\left\lfloor\dfrac{n}{i}\right\rfloor=d$ is equivalent to

This is further equivalent to

Using $i\in\mathbf N_+$, we can take the floor of this inequality, making it equivalent to

For $m\in D(n)$, $D(m)\subseteq D(n)$.

Let $m = \left\lfloor\dfrac{n}{k}\right\rfloor$. Then, for every $i\in\mathbf N_+$,

so $D(m)\subseteq D(n)$. The second equality uses the property of the floor function for nested fractions.

For a positive integer $n$ and positive real numbers $\alpha, \beta$, let

Then,

1. $|D(n,\alpha,\beta)|\le 2n^{\alpha/(1+\beta)}$.

2. For $d\in D(n,\alpha,\beta)$, the range of $\left\lfloor\dfrac{n^\alpha}{i^\beta}\right\rfloor=d$ satisfying $i$ is

   $$\left\lfloor\dfrac{n^{\alpha/\beta}}{(d+1)^{1/\beta}}\right\rfloor + 1\le i \le \left\lfloor\dfrac{n^{\alpha/\beta}}{d^{1/\beta}}\right\rfloor.$$

For the first point, consider two cases:

• When $i\le \dfrac{n^\alpha}{i^\beta}$, we have $i\le n^{\alpha/(1+\beta)}$, so there are at most $\left\lfloor\dfrac{n^\alpha}{i^\beta}\right\rfloor$ possible values of $n^{\alpha/(1+\beta)}$.
• When $i > \dfrac{n^\alpha}{i^\beta}$, we have $i> n^{\alpha/(1+\beta)}$, so $\dfrac{n^\alpha}{i^\beta} < n^{\alpha/(1+\beta)}$, and there are again at most $\left\lfloor\dfrac{n^\alpha}{i^\beta}\right\rfloor$ possible values of $n^{\alpha/(1+\beta)}$.

Combining the two cases gives $|D(n,\alpha,\beta)|\le 2n^{\alpha/(1+\beta)}$.

For the second point, $\left\lfloor\dfrac{n^\alpha}{i^\beta}\right\rfloor=d$ is equivalent to

Taking floors of this inequality gives the second statement.

Based on the analysis above, all positions with the same $\left\lfloor\dfrac ni\right\rfloor$ can be calculated together. The time complexity is $O(T\sqrt n)$.

#include <iostream>

long long H(int n) {
  long long res = 0;  // store the result
  int l = 1, r;       // left and right endpoints of the block
  while (l <= n) {
    r = n / (n / l);  // calculate the right endpoint of the current block
    // Accumulate this block's contribution to the result. Multiplying by 1LL prevents overflow
    res += 1LL * (r - l + 1) * (n / l);
    l = r + 1;  // move the left endpoint to the next block
  }
  return res;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int t, n;
  std::cin >> t;
  while (t--) {
    std::cin >> n;
    std::cout << H(n) << '\n';
  }
  return 0;
}

Let $a_0=0$. Suppose killing the first $(i-1)$ monsters requires $T(k,i-1)$ attacks, and the health of the $i$-th monster is $a_i$. Since killing the $(i-1)$-th monster requires attacking it $\lceil a_{i-1}/k\rceil$ times, all these attacks can extend to the $i$-th monster. Therefore, to kill the $i$-th monster, only $\max\{0,\lceil a_i/k\rceil-\lceil a_{i-1}/k\rceil\}$ more attacks are needed. Thus, the total number of attacks is

Since the $n,k$ involved in the problem can be large, calculating this sum separately for every $k$ is infeasible. We can maintain the sequence $i=1,2,\cdots,n$ for every $\{T(k,i)\}_k$. Initially, let $T(k,0)\equiv 0$. Suppose the sequence $\{T(k,i-1)\}_k$ is known. To obtain $\{T(k,i)\}_k$, according to the analysis above, we only need to add $k$ to the $\max\left(0,\left\lceil\dfrac{a_i}{k}\right\rceil-\left\lceil\dfrac{a_{i-1}}{k}\right\rceil\right)$-th term. Using multidimensional number-theoretic block decomposition, this modification can be divided into $O(\sqrt{a_{i-1}}+\sqrt{a_i})$ interval modification operations, with a fixed value added on each interval. The resulting sequence $\{T(k,n)\}_k$ is the answer.

Since the problem involves a series of interval-addition operations and queries occur only after all modifications are complete, a difference sequence can be maintained for interval-addition modifications, and the required sequence can finally be obtained by taking prefix sums. The total time complexity is $O(\sum\sqrt{a_i})$. This problem also has other solutions.

#include <algorithm>
#include <iostream>

constexpr int N = 100009;
int n, a[N], maxn;
long long ans[N];

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n;
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
    maxn = std::max(maxn, a[i]);
  }
  for (int i = 0; i < n; ++i)
    for (int l = 1, r;; l = r + 1) {
      r = std::min(l < a[i] ? (a[i] - 1) / ((a[i] - 1) / l) : N,
                   l < a[i + 1] ? (a[i + 1] - 1) / ((a[i + 1] - 1) / l)
                                : N);  // two-dimensional number-theoretic block decomposition
      if (r == N) break;
      int x = (a[i + 1] - 1) / l - std::max(a[i] - 1, 0) / l;
      if (x > 0) ans[l] += x, ans[r + 1] -= x;  // accumulate contribution
    }
  ++ans[0];  // the formula ⌈a/l⌉=(a-1)/l+1 does not hold when a=0, so it needs to be corrected
  for (int i = 1; i <= maxn; ++i)
    std::cout << (ans[i] += ans[i - 1]) << " \n"[i == maxn];
  return 0;
}