CodeChef February 2016. Weird Sum 题解

这是 CodChef February Challenge 2016 上的一题，题目链接在这里：WRDSUM

给定一个整数 $n(n \geq 2)$，考虑其质因子分解 $n = p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$

记 $g = \text{gcd}(k_1, k_2, \cdots, k_r)$ 且 $m_i = \frac{k_i}{g}$

定义函数 $F(n) = p_1^{m_1}p_2^{m_2}\cdots p_r^{m_r}$

现在给定一个整数 $N(N \leq 10^{2016})$，你需要计算

$$S = F(2) + F(3) + \cdots + F(N)$$

答案对 $998244353$ 取模

首先看这题 $N$ 这么大，而且单个数的 $F$ 是不容易计算的因为要计算你肯定要分解它，那么肯定是要推推式子了

一个想法就是先枚举最大公因数 $g$，而且可以肯定 $g$ 是不可能太大的，最多是在 $\mathcal O(\log N)$ 级别，看起来很靠谱！那么 $S$ 可以写成这样（为了方便，我把质因子分解都写成 $p_1^{k_1}p_2^{k_2}p_3^{k_3}$ 这样的形式）

$$S = \sum_{g \geq 1} \sum_{p_1^{m_1g}p_2^{m_2g}p_3^{m_3g} \leq N} p_1^{m_1}p_2^{m_2}p_3^{m_3} [(m_1, m_2, m_3) = 1]$$

说明一下，这里 $[...]$ 这样的记号表示，如果里面的条件成立那么值是 $1$，否则是 $0$

现在看到一个非常不舒服的一项就是那个 $[(m_1, m_2, m_3) = 1]$，因为这样一个条件表达式根本没法化简，但是我们可以用莫比乌斯反演把它替换

$$[(m_1, m_2, m_3) = 1] = \sum_{d | (m_1, m_2, m_3)} \mu(d)$$

把上面的式子代入就是

$$S = \sum_{g \geq 1} \sum_{p_1^{m_1g}p_2^{m_2g}p_3^{m_3g} \leq N} p_1^{m_1}p_2^{m_2}p_3^{m_3}\sum_{d | (m_1, m_2, m_3)} \mu(d)$$

然后我们可以更换求和顺序，改为先对 $d$ 求和

$$S = \sum_{d \geq 1} \mu(d) \sum_{g \geq 1} \sum_{p_1^{m_1g}p_2^{m_2g}p_3^{m_3g} \leq N} p_1^{m_1}p_2^{m_2}p_3^{m_3} [d | (m_1, m_2, m_3)]$$

这样 $m_1, m_2, m_3$ 就都是 $d$ 的倍数，那么我们设 $m_i = ds_i$，就可以变成

$$S = \sum_{d \geq 1} \mu(d) \sum_{g \geq 1} \sum_{p_1^{s_1gd}p_2^{s_2gd}p_3^{s_3gd} \leq N} p_1^{s_1d}p_2^{s_2d}p_3^{s_3d}$$

注意到这时候对于 $p_1^{s_1}p_2^{s_2}p_3^{s_3}$ 来说唯一的限制就是它要不大于 $N$，那么我们令 $i = p_1^{s_1}p_2^{s_2}p_3^{s_3}$ 就可以得到

$$S = \sum_{d \geq 1} \mu(d) \sum_{g \geq 1} \sum_{2 \leq i^{dg} \leq N} i^d$$

这时候式子已经很清楚了，最里面是一个幂和，具体可以参考我的这篇文章，那么现在来考虑一下外面两个求和的次数，也就是有多少整数对 $(d, g)$ 满足 $2^{dg} \leq N$，如果我们记 $M = \log_2 N$ 的话，这个数大约就是

$$\frac{M}{1} + \frac{M}{2} + \cdots + \frac{M}{M} \approx M\ln M$$

那么现在来考虑最里面那个幂和，我们记 $G_d(n) = \sum_{i=2}^n i^d$，把式子改写成

$$S = \sum_{d \geq 1} \mu(d) \sum_{g \geq 1} G_d(\lfloor \sqrt[dg]{N} \rfloor)$$

现在有两种计算方法，一种是上面文章提到的 $\mathcal O(d^2)$ 的方法，另一种是直接暴力快速幂计算 $\mathcal O(\lfloor \sqrt[dg]{N} \rfloor \log d)$

我们发现，当 $d$ 很大的时候 $\lfloor \sqrt[dg]{N} \rfloor$ 是很小的，因此这时候暴力就好了，如果 $\lfloor \sqrt[dg]{N} \rfloor$ 很大的话，$d$ 就会变得很小，这时候就可以用平方的方法计算

现在问题就剩下一个了，如何预处理 $N$ 的开方，答案是直接二分，但是你需要不断地优化常数，我在这里说说一些细节

刚开始的时候我是压 $3$ 位写了 FFT，结果一直跑不过，后来改成了压 $7$ 位暴力乘结果过了…… 至于原因嘛，因为这里压完位就只有一两百位数的乘法，FFT 常数太大

然后关于计算开方那里，由于我们是要计算开 $2, 3, 4, \cdots$ 次方一直到开到 $1$ 为止，那么如果我们要计算的是开 $m$ 次方，并且 $m$ 刚好不是质数，设 $m = pd$，$p$ 是它的最小质因子，我们可以利用之前已经计算过的 $R = \lfloor \sqrt[d]{N}\rfloor$，现在来分析一下误差有多少，首先可以知道

$$R \leq \sqrt[d]{N} < R + 1$$

那么继续开方的话就会变成

$$\sqrt[p]{R} \leq \sqrt[pd]{N} < \sqrt[p]{R + 1}$$

可以看出来绝对误差不会超过 $1$，所以只要计算 $\lfloor \sqrt[p]{R} \rfloor$，之后再检验一下之后那个数是不是还满足条件就可以了，这样会优化掉很大部分时间

再来是在计算的时候，由于一个数开方到后面有很多都是相同的数，而且这些数都是连续的区间，那么当出现两个数相同的时候我们就改为二分这个区间的右端点

关于二分的初始区间，粗略的估计可以用这个数的位数除以要开方的次数，由于结果是递减的，右端点可以用前面一次的结果，然后最精细的，你观察一下 $N$ 最多有 $2000$ 多位，这在 long double 的范围内，你可以用 long double 来计算出一个 $N$ 的近似值开方完用最高位，低位取 $0$ 作为下界，如果怕有精度误差，最高位减一就可以了，实际的上下界就用上面最紧的一个

最后关于幂和的计算，实际上 $\mathcal O(d^2)$ 还可以优化成 $\mathcal O(d)$ 的，详情请看特殊多项式在整点上的线性插值方法

到此为止，这题就可以解决了，CodeChef 上最大点给了 7s，我交上去跑了 1.4s 还算挺快的

代码有点丑…… 凑和着看吧