Solution - Atcoder Xmas2019E Sum of f(n)

考虑 \(F(n) = \sum\limits_{i = 1}^n f_i = \sum\limits_{i = 1}^n \sum\limits_{p\in \mathbb{P}, k\ge 1} [p^k | i] = \sum\limits_{p\in \mathbb{P}, k\ge 1} \lfloor\frac{n}{p^k}\rfloor\)。

对于这个 \(\lfloor\frac{n}{x}\rfloor\)，一个比较经典的想法就是考虑对其整除分块，然后统计有多少个 \(p^k(p\in \mathbb{P}, k\ge 1)\) 在一个给定的区间 \((\lfloor\frac{n}{x}\rfloor, \lfloor\frac{n}{y}\rfloor]\) 里。

对于这个 \(p^k\)，若 \(k > 1\) 做着便有些棘手，但是考虑到对于 \(k > 1\)，\(p^k\) 的数量是极少的。
因为此时至少有 \(p\le \sqrt{n}\)，所以 \(p\) 的数量是 \(\mathcal{O}(\frac{\sqrt{n}}{\log \sqrt{n}})\) 级别的，\(p^k(k > 1)\) 的数量的一个宽松的上界 \(\mathcal{O}(\sqrt{n})\)，这部分直接暴力算即可。

于是接下来就只需要对 \(p\in \mathbb{P}\) 计数了。
然后对于这部分的求和，考虑前缀和的形式，变为求 \([1, \lfloor\frac{n}{x}\rfloor]\) 内质数的个数。
这部分就是经典的 Min25 筛的运用 LibreOJ 6235 区间素数个数。

时间复杂度 \(\mathcal{O}(\frac{n^\frac{3}{4}}{\log n})\)。

#include<bits/stdc++.h>
using ll = long long;
const ll limn = 1e11, limB = (ll)sqrt(limn);
ll n, B;
int pr[limB + 1], vis[limB + 1], cnt;
int leq[limB + 1], geq[limB + 1], tot;
ll val[limB * 2 + 1], g[limB * 2 + 1];
inline int &id(ll x) {return x <= B ? leq[x] : geq[n / x];}
int main() {
   scanf("%lld", &n), B = sqrt(n);
   for (ll l = 1, r; l <= n; l = r + 1) {
      r = n / (n / l);
      val[id(n / l) = ++tot] = n / l, g[tot] = n / l - 1;
   }
   ll ans = 0;
   for (int i = 2; i <= B; i++) {
      if (! vis[i]) {
         for (int j = 1; j <= tot && val[j] >= 1ll * i * i; j++)
            g[j] -= g[id(val[j] / i)] - g[id(pr[cnt])];
         pr[++cnt] = i;
         for (ll x = 1ll * i * i; x <= n; x *= i)
            ans += n / x;
      }
      for (int j = 1; j <= cnt && i * pr[j] <= B; j++) {
         vis[i * pr[j]] = 1;
         if (i % pr[j] == 0)
            break;
      }
   }
   for (ll l = 1, r; l <= n; l = r + 1) {
      r = n / (n / l);
      ans += (n / l) * (g[id(r)] - g[id(l - 1)]);
   }
   printf("%lld\n", ans);
   return 0;
}