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 = pdp 是它的最小质因子,我们可以利用之前已经计算过的 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 还算挺快的

Screenshot from 2016-02-13 18-11-38

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

 

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2016/02/codechef-february-2016-weird-sum

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

One thought on “CodeChef February 2016. Weird Sum 题解

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.