EOJ #49 题解

kblack edited 6 年，10 月前

原题目参见：传送门

显然对于一组 $(x, y)$，$f(x, y)$ 至少需要被计算一次，所以可以考虑计算出 $(x, y, t = f(x, y))$ 后直接对这些三元组进行排序即可，排序的时间复杂度 $O(n \log n)$，在全部数据据范围内都不会成为运行时间的瓶颈。

由此，重点就在于如何快速地计算得到 $f(x, y)$，几个子任务的数据规模，也是按照对于计算过程的渐进时间复杂度要求来设计的，以下记 $y_{max} = m$，$y_{max}-x_{min}+1 = l$。

对于前 $20\%$ 的数据，对于每对 $(x, y)$，循环遍历 $x \leq p \leq y$，判断 $p$ 是否是质数，是的话就累加得到 $t$，使用朴素的方法判断 $p$ 是否为质数，时间复杂度 $O(\sqrt m)$ 到 $O(m)$，时间复杂度 $O(nm^{1.5})$ 或 $O(nm^2)$，足够通过这 $2$ 个测试点。

对于前 $40\%$ 的数据，注意到每个数字是否是素数也是可以缓存的，通过预先检查范围内的数字是否为素数，我们可以将时间复杂度降低到 $O(nm+m^{1.5})$ 或 $O(nm+m^2)$，足够通过这 $2$ 个测试点。

对于前 $60\%$ 的数据，从这里开始，我们需要运用一些数学技巧来帮助我们更快地计算 $f(x,y)$，在这 $2$ 个测试点中，我们需要用到名为前缀和的技巧。定义辅助函数 $g(x) = \sum_{i=0}^{x}{isprime(p)p}$，其中 $isprime(x) = 1$ 当且仅当 $x$ 为质数，否为值为 $0$，特别的，我们定义 $isprime(0) = 0$。注意到 $f(x, y) = g(y) - g(x-1)$，于是接下来我们只要快速地算出 $g(x)$ 即可。由 g(x)的递推式 $g(x) = g(x-1) + isprime(x)x$，$(x \geq 1)$，我们可以通过对 $1$ ~ $m$ 的遍历以 $O(m^{1.5})$ 的复杂度求得 $g(x)$，于是求所有 $f(x, y)$的复杂度被降低到了 $O(n+m^{1.5})$，足够通过这 $2$ 个测试点。

对于前 $90\%$ 的数据，计算 $isprime(x)$ 终于成为了瓶颈，所以我们要以更高的效率批量地计算出 $isprime(x)$，这类算法叫做素数筛法，大家可以参考网上的资料，例如算法之素数筛法，使用线性筛可以将求所有 $isprime(x)$ 的复杂度降低到 $O(m)$，进而计算 $f(x,y)$ 的复杂度降低到 $O(n+m)$ 足够通过这三个数据点。

对于最后一个测试点，观察数据，发现 $x_{min}$ 与 $y_{max}$ 的最大差值（相对于 $10^{12}$）不太大，又由于我们只需要 $g(x)$ 的相对差值，我们可以重新定义 $g(x) = g(x-1) + isprime(x)*x$，$(x \geq x_{min})$，$g(x_{min}-1)=0$。于是现在问题就在于如何快速地求出 $isprime(x)$，$x_{min} \leq x \leq y_{max}$。

注意到在对于一个正整数 $p$，在 $x$~$y$ 间，每 $p$ 个数会出现一个 $p$ 的倍数 $kp$，而当 $k \neq 1$时，我们就可以断言 $kp$ 是一个和数。对于一个数 $x \leq m$，如果他是一个和数，则他必然有至少一个因子 $p \leq \sqrt m$，所以对于 $x_{min} \leq x \leq y_{max}$，我们只要筛去所有 $2 \leq p \leq \sqrt m$ 的倍数，剩下的就都是质数了。对于每个 $p$，他至多会筛去 $\lceil \frac{l}{p} \rceil$ 个数，所以我们一共会筛去（因为有一部分数会被重复筛去）$\sum_{p=2}^{\lfloor \sqrt m \rfloor} {\lceil \frac{l}{p} \rceil}$，我们可以证明，这个数量的渐进复杂度为 $O(\sqrt m + l \log l)$，最后的时间复杂度是 $O(n \log n + n +\sqrt m + l \log l)$，足够通过此题。实际上，通过只使用 $\leq \sqrt m$ 的质数作为筛法使用的 $p$，还能进一步减小算法的常数。

以下给出这个筛法的核心代码，可以供参考：

base = minx-1; // 数组不可能分配 10^12 的大小，所以人工添加偏差值，只使用需要的 10^6 大小的空间
for(ll i = minx; i<=maxy; ++i) isprime[i-base] = 1; // 默认每个数都是质数
if(minx==1) isprime[1] = 0; // 特判 1 不是质数
for(int i = 2; i<M; ++i) {
    ll p = minx-minx%i;
    if(p<minx) p+=i;
    if(p==i) p+=i; // 得到范围内第一个不等于 i 的 i 的倍数
    while(p<=maxy) isprime[p-base] = 0, p+=i; // 依次筛去范围内所有 i 的倍数
}
for(ll i = 1; i<=maxy-minx+1; ++i) g[i] = g[i-1] + isprime[i]*(i+base);