Number Theory Block

Number-theoretic blocking can quickly compute sums of the form

\[ \sum_{i=1}^nf(i)g\left(\left\lfloor\dfrac ni\right\rfloor\right) \]

If \(\sum_{i=l}^{r}f(i)\) can be computed in \(O(1)\) time or the prefix sum of \(f\) has been preprocessed, number-theoretic blocking can compute the value of the above sum in \(O(\sqrt{n})\) time.

Number-theoretic blocking is often combined with techniques like Möbius inversion.

Idea

First, this article illustrates the idea of number-theoretic blocking with a simple example. Suppose we want to compute the number of integer points under the hyperbola as shown:

This is equivalent to computing the sum:

\[ \sum_{i=1}^{11}\left\lfloor\dfrac{11}{i}\right\rfloor. \]

This is a special case of the sum shown earlier when \(f(k)=1,~g(k)=k\).

The simplest approach is to compute column by column and then sum, but this requires computing the number of integer points in each column \(i=1,2,\cdots,11\). Observing the figure, we can see that these integer point columns can be divided into \(5\) blocks. Within each block, the column heights are the same, forming a rectangular point array. Therefore, as long as we know the widths of these blocks, we can quickly complete the count by computing the sizes of these rectangular blocks.

This is the basic idea of integer division blocking.

Properties

This section discusses several conclusions about the blocking of integer points under the hyperbola \(y = \dfrac{n}{x}\). Specifically, we need to divide the integers from \(1\) to \(n\) into several blocks according to the value of \(\left\lfloor\dfrac{n}{i}\right\rfloor\). Let

\[ D(n) = \left\{\left\lfloor\dfrac{n}{i}\right\rfloor : 1 \le i \le n,~i\in\mathbf N_+\right\}. \]

This is the set of all possible values of \(\left\lfloor\dfrac{n}{i}\right\rfloor\).

First, there are only \(O(\sqrt{n})\) distinct such values. Therefore, the number of blocks obtained by number-theoretic blocking is only \(O(\sqrt{n})\).

Property 1

\(|D(n)|\le 2\sqrt{n}\)．

Proof

Consider two cases:

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

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

Through more detailed analysis, we can precisely describe the set \(D(n)\) and its size.

Property 2

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

\[ 1 < 2 < \cdots < s-1 < s \le \left\lfloor\dfrac{n}{s}\right\rfloor < \left\lfloor\dfrac{n}{s-1}\right\rfloor < \cdots < \left\lfloor\dfrac{n}{2}\right\rfloor < \left\lfloor\dfrac{n}{1}\right\rfloor = n. \]

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

Proof

First, for \(1 \le i \le s\), we can prove \(\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\). Writing as inequalities, this is equivalent to: given \(d \le \dfrac{n}{i} < d + 1\), prove \(i \le \dfrac{n}{d} < i + 1\). The given condition can be written as \(i\le\dfrac{n}{d} < i + \dfrac{i}{d}\). Therefore, we only need to prove \(\dfrac{i}{d} \le 1\), i.e., \(i \le d = \left\lfloor\dfrac{n}{i}\right\rfloor\). This is equivalent to \(i \le \dfrac{n}{i}\), which holds for all \(1 \le i \le s \le \sqrt{n}\).

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

To obtain the final expression for \(|D(n)|\), we need to examine 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\), i.e., \(s^2 \le n < s^2+s\). Then, \(4s^2 + 1 \le 4n + 1 < 4s^2+4s+1 = (2s+1)^2\). Since \(4n+1\) is always odd, the left side can be equivalently relaxed to \(4s^2\), so this condition is equivalent to \(2s \le \sqrt{4n+1} < 2s+1\), i.e., \(\lfloor \sqrt{4n+1}\rfloor = 2s\).
• When \(s < \left\lfloor\dfrac{n}{s}\right\rfloor\), we always have \(s + 1 \le \dfrac{n}{s}\), i.e., \(s^2 + s\le n\). Also \(n < (s+1)^2\), so \(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 that \(4n+1\) is odd, the right side can be equivalently tightened to \(4(s+1)^2\), so this condition is equivalent to \(2s+1\le\sqrt{4n+1} < 2s+2\), i.e., \(\lfloor \sqrt{4n+1}\rfloor = 2s+1\).

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

Next, the left and right endpoints of a single block are easy to determine.

Property 3

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

\[ \left\lfloor\dfrac{n}{d+1}\right\rfloor + 1\le i \le \left\lfloor\dfrac{n}{d}\right\rfloor. \]

Proof

\(\left\lfloor\dfrac{n}{i}\right\rfloor=d\) is equivalent to the inequality

\[ d\le \dfrac{n}{i} < d+1. \]

This further implies

\[ \dfrac{n}{d+1} < i\le \dfrac{n}{d}. \]

Using \(i\in\mathbf N_+\), we can take the floor of this inequality, which is equivalent to

\[ \left\lfloor\dfrac{n}{d+1}\right\rfloor + 1 \le i\le \left\lfloor\dfrac{n}{d}\right\rfloor. \]

This property also reflects the symmetry of the graph: the set of right endpoints (green points in the previous figure) of each block is exactly \(D(n)\). This is easy to understand because the entire graph is symmetric about the line \(y=x\).

In addition to these properties, the set \(D(n)\) also has good recursive properties:

Property 4

For \(m\in D(n)\), we have \(D(m)\subseteq D(n)\).

Proof

Let \(m = \left\lfloor\dfrac{n}{k}\right\rfloor\). Then, for all \(i\in\mathbf N_+\), we have

\[ \left\lfloor\dfrac{m}{i}\right\rfloor = \left\lfloor\dfrac{\lfloor n/k\rfloor}{i}\right\rfloor = \left\lfloor\dfrac{n}{ki}\right\rfloor \in D(n), \]

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

As mentioned earlier, \(D(n)\) is both the set of values of \(\left\lfloor\dfrac{n}{i}\right\rfloor\) in each block and the set of right endpoints of each block. This means that if we want to recursively apply number-theoretic blocking (i.e., the function's value at \(n\) depends on its values at \(m\in D(n)\setminus\{n\}\)), then the set of values and right endpoints involved throughout the computation are actually \(D(n)\). A typical example is the Du Sieve.

Procedure

Using the conclusions from the previous section, we obtain the specific procedure for number-theoretic blocking.

To compute the sum

\[ \sum_{i=1}^nf(i)g\left(\left\lfloor\dfrac ni\right\rfloor\right) \]

we can divide the indices \(i=1,2,\cdots,n\) into blocks according to the value of \(\left\lfloor\dfrac ni\right\rfloor\). Since indices with the same \(\left\lfloor\dfrac ni\right\rfloor\) value form a contiguous interval \([l,r]\), the value of the sum for that block is

\[ \left(\sum_{i=l}^rf(i)\right)\cdot g\left(\left\lfloor\dfrac nl\right\rfloor\right). \]

To compute this sum quickly, we usually need to be able to quickly compute the left-hand sum over \(f\). Sometimes, the expression for this sum is known and can be computed in \(O(1)\) time per block; other times, its prefix sum can be preprocessed, allowing \(O(1)\) time per query.

When sequentially computing the left and right endpoints of each block, the left endpoint \(l\) of the current block equals the right endpoint of the previous block plus \(1\), and the right endpoint of the current block equals \(\left\lfloor\dfrac n{\lfloor n/l\rfloor}\right\rfloor\). Thus, we obtain the following pseudocode:

\[ \begin{array}{l} \textbf{Algorithm }\text{Sum}(f,g,n):\\ \textbf{Input. }n,~s(k)=\sum_{i=1}^kf(k),~g(k).\\ \textbf{Output. }S(n) = \sum_{i=1}^nf(i)g(\lfloor n/i\rfloor).\\ \textbf{Method.}\\ \begin{array}{ll} 1 & l \gets 1\\ 2 & \textit{result} \gets 0 \\ 3 & \textbf{while } l \leq n \textbf{ do}\\ 4 & \qquad r \gets \left\lfloor \dfrac{n}{\lfloor n/l \rfloor} \right\rfloor\\ 5 & \qquad \textit{result} \gets \textit{result} + (s(r)-s(l-1))\cdot g\left(\left\lfloor \dfrac{n}{l} \right\rfloor\right)\\ 6 & \qquad l \gets r+1\\ 7 & \textbf{end while}\\ 8 & \textbf{return }\textit{result} \end{array} \end{array} \]

Assuming the time complexity for a single computation of \(s(\cdot)\) is \(O(1)\), the overall time complexity is \(O(\sqrt{n})\).

Extensions

The previous discussion covers the most common and basic form of number-theoretic blocking. This section further discusses extended forms.

Ceiling Number-Theoretic Blocking

Number-theoretic blocking can be used to compute sums involving the ceiling function:

\[ \sum_{i=1}^nf(i)g\left(\left\lceil\dfrac ni\right\rceil\right). \]

Since \(\left\lceil\dfrac ni\right\rceil = \left\lfloor\dfrac {n-1}i\right\rfloor + 1\), this sum can be transformed into a floor function case:

\[ f(n)g(1) + \sum_{i=1}^{n-1}f(i)g\left(\left\lfloor\dfrac {n-1}i\right\rfloor + 1\right). \]

Note the change in the upper limit of the summation and the separate term for \(i=n\).

Multidimensional Number-Theoretic Blocking

Number-theoretic blocking can also handle sums containing more than one floor function:

\[ \sum_{i=1}^{n}f(i)g\left(\left\lfloor\dfrac {n_1}i\right\rfloor,\left\lfloor\dfrac {n_2}i\right\rfloor,\cdots,\left\lfloor\dfrac {n_m}i\right\rfloor\right). \]

To apply the idea of number-theoretic blocking, we need to ensure that within each block, the values of all floor functions \(\left\lfloor\dfrac {n_1}i\right\rfloor,\left\lfloor\dfrac {n_2}i\right\rfloor,\cdots,\left\lfloor\dfrac {n_m}i\right\rfloor\) remain unchanged. That is, a multidimensional block should be the intersection of all one-dimensional blocks. For this, given the left endpoint \(l\), the corresponding right endpoint is

\[ \min\left\{\left\lfloor\dfrac {n_1}{\lfloor n_1/l\rfloor}\right\rfloor,\left\lfloor\dfrac {n_2}{\lfloor n_2/l\rfloor}\right\rfloor,\cdots,\left\lfloor\dfrac {n_m}{\lfloor n_m/l\rfloor}\right\rfloor\right\}. \]

In other words, take the minimum of the right endpoints of all one-dimensional blocks as the right endpoint of the multidimensional block. The following diagram helps illustrate:

The two-dimensional form is more common. In this case, replace \(r \gets \left\lfloor \dfrac{n}{\lfloor n/l \rfloor}\right\rfloor\) in the pseudocode with

\[ r \gets \min\left\{\left\lfloor \dfrac{n_1}{\lfloor n_1/l \rfloor}\right\rfloor,\left\lfloor \dfrac{n_2}{\lfloor n_2/l \rfloor}\right\rfloor\right\}. \]

Arbitrary Exponent Number-Theoretic Blocking

Number-theoretic blocking can be used for sums involving floor functions with arbitrary exponents:

\[ \sum_{i=1}^{\lfloor n^{\alpha/\beta}\rfloor}f(i)g\left(\left\lfloor\dfrac {n^\alpha}{i^\beta}\right\rfloor\right). \]

Here, \(\alpha,\beta\) are positive real numbers. The basic form discussed earlier corresponds to \(\alpha=\beta=1\).

Property

For positive integer \(n\) and positive real numbers \(\alpha, \beta\), let

\[ D(n,\alpha,\beta) = \left\{\left\lfloor\dfrac{n^\alpha}{i^\beta}\right\rfloor: i=1,2,\cdots,\lfloor n^{\alpha/\beta}\rfloor\right\}. \]

Then,

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

2. For \(d\in D(n,\alpha,\beta)\), the range of \(i\) satisfying \(\left\lfloor\dfrac{n^\alpha}{i^\beta}\right\rfloor=d\) 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. \]

Proof

For the first point, consider two cases:

• When \(i\le \dfrac{n^\alpha}{i^\beta}\), we have \(i\le n^{\alpha/(1+\beta)}\), so \(\left\lfloor\dfrac{n^\alpha}{i^\beta}\right\rfloor\) has at most \(n^{\alpha/(1+\beta)}\) distinct values.
• When \(i > \dfrac{n^\alpha}{i^\beta}\), we have \(i> n^{\alpha/(1+\beta)}\), and thus \(\dfrac{n^\alpha}{i^\beta} < n^{\alpha/(1+\beta)}\), so \(\left\lfloor\dfrac{n^\alpha}{i^\beta}\right\rfloor\) also has at most \(n^{\alpha/(1+\beta)}\) distinct values.

Combining both cases, we have \(|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

\[ d \le \dfrac{n^\alpha}{i^\beta} < d+1 \iff \dfrac{n^{\alpha/\beta}}{(d+1)^{1/\beta}} < i \le \dfrac{n^{\alpha/\beta}}{d^{1/\beta}}. \]

Taking the floor of this inequality yields the second proposition.

Using these properties, we can perform number-theoretic blocking for arbitrary exponents in \(O(n^{\alpha/(1+\beta)})\) time complexity.

Example

For example, for the sum with \(\alpha=\beta=1/2\):

\[ \sum_{i=1}^nf(i)g\left(\left\lfloor\sqrt{\dfrac {n}{i}}\right\rfloor\right), \]

it can be solved via number-theoretic blocking in \(O(n^{1/3})\) time. Given the left endpoint \(l\) of a block, the right endpoint can be computed as \(r=\left\lfloor\dfrac{n}{\lfloor\sqrt{n/l}\rfloor^2}\right\rfloor\).

Examples

UVa11526 H(n)

There are \(T\) test cases, each with an integer \(n\). For each test case, output \(\sum_{i=1}^n\left\lfloor\dfrac ni\right\rfloor\).

Solution

According to the previous analysis, we can compute together for each block where \(\left\lfloor\dfrac ni\right\rfloor\) is the same. The time complexity is \(O(T\sqrt n)\).

Implementation

#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
    // Add the contribution of this block to the result. Multiply by 1LL to prevent 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;
}

Codeforces 1954E Chain Reaction

There is a row of \(n\) monsters, each with initial health \(a_i\). One attack reduces the health of a contiguous segment of alive monsters by \(k\). Monsters with health not greater than \(0\) are considered dead. For all \(k\), find the number of attacks needed to kill all monsters. Here, \(n,a_i\leq 10^5\).

Solution

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

\[ T(k,n)=\sum_{i=1}^n\max\left(0,\left\lceil\dfrac{a_i}{k}\right\rceil-\left\lceil\dfrac{a_{i-1}}{k}\right\rceil\right). \]

Since \(n\) and \(k\) in the problem are large, computing this sum separately for each \(k\) is not feasible. Consider maintaining the sequence \(\{T(k,i)\}_k\) for each \(i=1,2,\cdots,n\). Initially, set \(T(k,0)\equiv 0\). Suppose the sequence \(\{T(k,i-1)\}_k\) is known, consider how to modify it to obtain \(\{T(k,i)\}_k\). According to the analysis, we only need to add \(\max\left(0,\left\lceil\dfrac{a_i}{k}\right\rceil-\left\lceil\dfrac{a_{i-1}}{k}\right\rceil\right)\) to the \(k\)-th term of the sequence. Using two-dimensional number-theoretic blocking, this modification can be split into \(O(\sqrt{a_{i-1}}+\sqrt{a_i})\) interval modification operations, where the value added on each interval is constant. The final sequence \(\{T(k,n)\}_k\) is the answer.

Since the problem involves a series of range addition operations and queries only occur after all modifications are done, we can maintain a difference array for range additions and finally obtain the desired sequence by computing prefix sums. The total time complexity is \(O(\sum\sqrt{a_i})\). Other solutions exist for this problem.

Implementation

#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 theory block
      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, needs correction
  for (int i = 1; i <= maxn; ++i)
    std::cout << (ans[i] += ans[i - 1]) << " \n"[i == maxn];
  return 0;
}

Exercises

• UVa11526 H(n)
• Luogu P2261 CQOI2007 Remainder Sum
• Luogu P3455 POI2007 ZAP-Queries

References and Notes

• Time and Space Complexity Analysis of Du Sieve by riteme

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用