BZOJ 3944 Sum

发布于 2017-09-13  202 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3944

题意:欧拉函数,莫比乌斯函数前缀和,\(n\leq 2^{31}-1\)


人生中的第一次杜教筛= =

n 很大,显然不能线性筛了。现在只考虑莫比乌斯函数的前缀和,欧拉函数同理。

构造这么几个函数:

$$g(n)=\sum_{i=1}^{n}\mu (i)$$

$$f(n)=\sum_{d|n}^{ }\mu (d)$$

$$F(n)=\sum_{i=1}^{n}f(i)$$

很显然,\(F(n)=1+0+0+...+0=1\)。

另外,\(F(n)=\sum_{i=1}^{n}\mu (i)\cdot \left \lfloor \frac{n}{i} \right \rfloor=\sum_{i=1}^{n} g(\left \lfloor \frac{n}{i} \right \rfloor)\)

这是为什么呢,想想就知道,比如\(\mu (1)\) 出现了\(n\) 次,在每个\(g(\frac{n}{i})\) 中都出现了,\(\mu (2)\) 只出现了\(\left \lfloor \frac{n}{2} \right \rfloor\) 次,仅在\(\left \lfloor \frac{n}{i} \right \rfloor\geq 2\) 的\(g\) 中出现了,以此类推。

所以\(\sum_{i=1}^{n}g(\left \lfloor \frac{n}{i} \right \rfloor)=1\),那么\(g(n)=1-\sum_{i=2}^{n}g(\left \lfloor \frac{n}{i} \right \rfloor)\)

这玩意递归求解即可,但是直接上会 T。我们可以预处理出一些 n 比较小的前缀和,可以证明的是,预处理到\(n^{\frac{2}{3}}\) 处是最优的。

 


一个非常弱的准退役OIER