数论求和小记

· · 个人记录

听yyc讲课跟听天书一样，感觉不记点东西几星期就忘了，会先优先记听的不是很懂的东西。

前置知识：

设

T(n)=\sum_{i=1}^n \frac{1}{i^k}

用积分可证。

Powerful Number

powerful number定义为没有1次质因子的数

后文用 \texttt {PN} 来简称 powerful number

Theorem: [1,n] 中的 \texttt {PN} 个数是 O(\sqrt{n})

证明：显然所有 \texttt {PN} 可以表示为 a^2b^3 的形式（将所有次数为偶数的质因子放入 a 中，将所有次数为奇数的质因子放入 b 中）

考虑枚举 a 来看有多少个满足条件的 b，得

\begin{aligned} O(\sum_{a=1}^{\sqrt{n}} (n/a^2)^\frac{1}{3}))&=O(\sum_{a=1}^{\sqrt{n}} \frac{n^{\frac{1}{3}}}{a^\frac{2}{3}})\\ &=O(n\sum_{a=1}^{\sqrt{n}}\frac{1}{a^{\frac{2}{3}}})\\ &=O(n^{\frac{1}{3}}\times n^{\frac{1}{6}})\\ &=O(\sqrt n) \end{aligned}

有两个积性函数 f,g 满足 f(p)=g(p) ，给出 g 的基本和组，求 f 的基本和组。

考虑构造 h=g/f （狄利克雷除法）

又因为 $h$ 是一个积性函数，所以当 $h(x)$ 有值时当且仅当 $x$ 是 $\texttt {PN}$。 证明显然。 $$ \begin{aligned} S_f(n)&=\sum_{i=1}^{n}f(i)\\ &=\sum_{i=1}^{n}\sum_{d|i}h(d)g(i/d)\\ &=\sum_{d=1}^{n}h(d)\sum_{i=1}^{\lfloor n/d\rfloor}g(i))\\ &=\sum_{i=1}^{n}h(d)S_g(\lfloor n/d \rfloor) \end{aligned} $$ 因为 $h$ 只在 $O(\sqrt n)$ 个位置有值，直接暴力找出并计算就可以算出 $f$ 的基本和组了。 在 $g$ 的基本和组可以使用杜教筛算出的情况下我们可以在 $O(n^\frac{2}{3})$ 的时间复杂度求出 $f$ 的基本和组。 证明： $$ \begin{aligned} \sum_{i=1}^{n} \sum_{j=1}^{\sqrt[3]{n/i^2}} \left(\frac{n}{i^2j^3}\right)^{\frac{2}{3}}&=\sum_{i=1}^{n} \sum_{j=1}^{\sqrt[3]{n/i^2}}\frac{n^{\frac{2}{3}}}{i^{\frac{4}{3}}j^2}\\ &=n^{\frac{2}{3}}\sum_{i=1}^{n}\frac{1}{i^{\frac{4}{3}}} \sum_{j=1}^{\sqrt[3]{n/i^2}}\frac{1}{j^2}\\ &=n^{\frac{2}{3}}\sum_{i=1}^{n} \frac{1}{i^{\frac{4}{3}}}\times O(1)\\ &=n^{\frac{2}{3}}\sum_{i=1}^{n} \frac{1}{i^{\frac{4}{3}}}\\ &=n^{\frac{2}{3}} \end{aligned} $$