杜教筛小寄巧

模拟赛考到然后发现的奇怪玩意。

首先不难发现我们的杜教筛是需要记忆化搜索的，这就需要一个 map 或者 umap。前者多一只 log，而后者常数巨大。

同时我们发现一个事情，我们杜教筛过程中遇到的所有数 x 一定都可以表示成 \lfloor\frac nx\rfloor 的形式。这提示我们，可以用一个 id 方法来把这些数拍到一个不大的数组上，类似这样：

int id(int x) { return x < S ? x << 1 : n / x << 1 | 1; }

其中 S 是一个根号级别的量。

但接下来我们会发现一件神奇的事情：所有不超过 n 三分之二次方的 x 根本不会需要这个记忆化搜索。事实上，它们会被直接全都预处理出来。

如此一来，我们发现我们的三目的前半部分实际上就是废物，如此一来我们也不需要把两类穿插存储，全部使用 n/x 作为标识就可以了。这样我们的数组只需要三分之一次方的大小。在洛谷板子中，这个数组只有两百多（因为分解取了 10^7）。

最后代码就会类似这样。

ll gphi(int x) {
  if (x < N) return phi[x];
  int p = n / x;
  if (vst[p]) return val[p];
  ll ans = x * (x + 1ll) >> 1;
  for (unsigned l = 2, r; unsigned d = x / l; l = r + 1) {
    r = x / d;
    ans -= (r - l + 1) * gphi(d);
  }
  return vst[p] = true, val[p] = ans;
}