杜教筛小寄巧

模拟赛考到然后发现的奇怪玩意。 首先不难发现我们的杜教筛是需要记忆化搜索的，这就需要一个 map 或者 umap。前者多一只 log，而后者常数巨大。 同时我们发现一个事情，我们杜教筛过程中遇到的所有数 $x$ 一定都可以表示成 $\lfloor\frac nx\rfloor$ 的形式。这提示我们，可以用一个 `id` 方法来把这些数拍到一个不大的数组上，类似这样： ```cpp int id(int x) { return x < S ? x << 1 : n / x << 1 | 1; } ``` 其中 `S` 是一个根号级别的量。 但接下来我们会发现一件神奇的事情：所有不超过 $n$ 三分之二次方的 $x$ 根本不会需要这个记忆化搜索。事实上，它们会被直接全都预处理出来。 如此一来，我们发现我们的三目的前半部分实际上就是废物，如此一来我们也不需要把两类穿插存储，全部使用 `n/x` 作为标识就可以了。这样我们的数组只需要三分之一次方的大小。在洛谷板子中，这个数组只有两百多（因为分解取了 $10^7$）。 最后代码就会类似这样。 ```cpp 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; } ```