min_25 筛

约定

• \(\mathbf{P}\) 表示全体质数集合
• \(p_i\) 表示第 \(i\) 个质数，特别地，\(p_0 =1\)。
• \(\mathrm{lpf}_i\) 表示 \(i\)​ 的最小质因子。

计算数论函数 \(f(n)\)​​​​ 的前缀和，要求 \(f(p_i)\)​​​​ 是低阶多项式，且对于合数 \(n\)​​​​，\(f(n)\)​ 可以写成形如 \(f(n) = A(\mathrm{lpf}_n^e)B\left(\dfrac{n}{\mathrm{lpf_n^e}}\right)\)​​​​的式子，其中 \(A(p^e)\)​​​​ 可以快速求值或预处理。

当 \(f(n)\)​ 是积性函数时，\(A(p^e) = f(p^e), B(n) = f(n)\)​。

Part. 1

令 \[ g_k(n, i) = \sum_{j=1}^nj^k[j \in \mathbf{P} \ \mathrm{or}\ \mathrm{lpf}_j > p_i] \] 直观地，\(g_k(n, i)\) 表示埃式筛第 \(i\) 轮后剩余 \(n\) 以内的数的 \(k\) 次方之和。 \[ g_k(n, i) = \begin{cases} g_k(n, i - 1), & p_i^2 > n\\ g_k(n, i - 1) - p_i^k\left(g_k\left(\lfloor \dfrac{n}{p_i}\rfloor, i-1\right) - \sum_{j=1}^{i-1}p_j^k\right), & p_i^2 \leq n \end{cases} \] 直观地，考虑埃式筛第 \(i\) 轮：

• 如果 \(p_i^2>n\)，那么这一轮不会筛去任何数，于是 \(g_k(n, i) = g_k(n, i - 1)\) 。
• 如果 \(p_i^2\leq n\)，那么这一轮会筛去最小质因子等于 \(p_i\) 的数，所以要减去计算这些数的 \(k\) 次方之和，提出公因子 \(p_i^k\) 后可得上式。

递推求出 \(g_k(x, \infty)\)​​​​ 在所有 \(x = \lfloor \dfrac{n}{i}\rfloor\)​​​​​​ 处的取值，复杂度是 \(O\left(\dfrac{n^{\frac34}}{\log n}\right)\)​​。

// Calculate g(x, 0) on [n / i]
int m = 0;
for (LL i = 1, j; i <= n; i = j + 1) {
  val[++m] = n / i;
  j = n / val[m];
  g0[m] = (val[m] - 1) % P; // x - 1
  g1[m] = (val[m] + 2) % P * g0[m] % P * (P + 1 >> 1) % P; // 2 + 3 + ... + x
  if (val[m] <= sq) {
    id1[val[m]] = m;
  } else {
    id2[j] = m;
  }
}
  
// Calculate g(x, i)
for (int i = 1; i <= cnt; i++) {
  LL limit = 1LL * primes[i] * primes[i];
  for (int j = 1; val[j] >= limit; j++) {
    LL x = val[j] / primes[i];
    int k = x <= sq ? id1[x] : id2[n / x];
    g0[j] = (g0[j] + i - 1LL - g0[k]) % P;
    g1[j] = (g1[j] - 1LL * primes[i] * (g1[k] - primeSum[i - 1])) % P;
  }
}

Part. 2

令 \[ s(n, i) = \sum_{j=1}^nf(j)[\mathrm{lpf}_j > p_i] \] 即 \(s(n, i)\) 表示 \(n\) 以内最小质因子大于等于 \(p_i\) 的函数值之和。

则 \(f(x)\) 的前缀和为 \[ \sum_{i=1}^nf(i) = s(n, 1) + f(1) \] 考虑计算 \(s(n, i)\)。

由 Part. 1 可以快速计算质数的贡献 \(\sum_{j=p_i}^nf(j)[j \in \mathbf{P}] = \sum_{k}\mathrm{coef_k}\times g_k(n, \infty)\)。

考虑合数的贡献，以 \(f(n)\) 是积性函数为例，枚举最小质因子得到 \[ \sum_{j=i}^{p_j^2\leq n}\sum_{c=1}^{p_j^{c+1} \leq n}\left[ f\left(p^{k+1}\right)+ f\left(p_j^k\right)s\left( \left\lfloor \frac{n}{p_j^c} \right\rfloor, j+1 \right) \right] \] 所以 \[ s(n, i) = \begin{cases} \sum\limits_{j=i}^{p_j \leq n} f(p_j) + \sum\limits_{j=i}^{p_j^2\leq n}\sum\limits_{c=1}^{p_j^{c+1} \leq n}\left[ f\left(p^{k+1}\right)+ f\left(p_j^k\right)s\left( \left\lfloor \frac{n}{p_j^c} \right\rfloor, j+1 \right) \right], & p_i \leq n\\ 0, & p_i > n \end{cases} \] 递归求解。

最后修改于 2021-08-13