题解：CF1954E Chain Reaction

· · 题解

数论分块

问题

计算形如函数 H() 的式子：

H (n) = \sum_{i = 1} ^{n}f(i)*g(\lfloor \frac{n}{i}\rfloor)

注意到，我们可以将 \frac{n}{i} 相同的打包计算，以此降低时间复杂度。

结论

对于常数 n ,使得：

\lfloor \frac{n}{i}\rfloor = \lfloor \frac{n}{j} \rfloor

其中，满足条件的最大的 j 为 \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor 。

扩展——向上取整

由于：

\lceil \frac{n}{i} \rceil = \lfloor \frac{n-1}{i} \rfloor +1

所以， n 的上取整分块与 n-1 的下取整分块是一样的,即：

\lceil \frac{n}{i} \rceil 所在块的右端点为 \lfloor \frac{n-1}{\lfloor \frac{n-1}{i} \rfloor} \rfloor

ps: 一定要注意 0 的情况不符合公式

扩展——二维数论分块

本质上就是多了一个限制条件，保证两个限制条件都能取到即可。

题解：CF1954E Chain Reaction

代码（摘自 oi.wiki）

#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);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    maxn = 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);  // 二维数论分块
      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;  // 累加贡献
    }
  ++ans[0];  // ⌈a/l⌉=(a-1)/l+1的式子当a=0时不成立，需要修正（就是最初最前面的位置会因为0的存在多减去1）
  for (int i = 1; i <= maxn; ++i)
    cout << (ans[i] += ans[i - 1]) << " \n"[i == maxn];
  return 0;
}

完结撒花！！！