简单数论普及

· · 科技·工程

我发现很多人不会这些很简单的东西

Part1.

给定 f(n),g(n) 均为积性函数求h(n)=\sum\limits_{d|n}f(d)g(\frac{n}{d})

易知 h(n) 也为积性函数，但有时h(p^k)的形式很麻烦怎么办？

注意到 h(p^k)=\sum\limits_{i=0}^kf(p^i)g(p^{k-i})

直接暴力求可以 O(k) 求出

p^k$的个数只有$O(\frac{n}{\ln n}) p^k,k\geq 2$的个数只有$O(\sqrt{n})

显然暴力求出所有的h(p^k),时间复杂度为O(\frac{n}{\ln n})

总复杂度为O(n)

由上知只要f(p^k)可由关于k多项式时间内求出

总复杂度仍为O(n)

Part2.

求f(n)=n^n

此时f不是积性函数

法一：

$h(n)=n\log_{g}n$ 有 $f(n)=g^{h(n)}

后半部分可以用光速幂解决

时间复杂度为O(\sqrt{p}),O(n)

只用求\log_{g}i,1\leq i \leq n

经典问题见模板，使用BSGS

时间复杂度为O(\frac{p^\frac{3}{4}}{\sqrt{\ln p}}),O(n)

总复杂度为O(\frac{p^\frac{3}{4}}{\sqrt{\ln p}}+n)

法二：

当n为合数时，n=ab且a,b>1

不妨令a<b 有 a\leq \sqrt{n}

f(n)=(ab)^{ab}=(a^ab^a)^b=(a^a)^b(b^b)^a=f(a)^bf(b)^a

预处理f(p)=p^p,p\in prime

时间复杂度为O(n)

对每个a\leq \sqrt{n}预处理出a^0,a^1\dots,a^{B-1}和a^B,a^{2B}\dots,a^{\lfloor \frac{N}{B}\rfloor B}

取B=\sqrt{n} 时间复杂度为O(n)

设a(n) 为 n 的最小素因子

考虑线性筛的过程我们有O(\sum\limits_{i=1}^n\ln a(i))的做法！

不幸的是O(\sum\limits_{i=1}^n\ln a(i))=O(n\ln n)

冷静想想不用原根我们很难对f(q)^p加速，其中p固定q变化

反过来令p变化q固定！

光速幂？但这里有1\leq f(q)\leq n

考虑做差记录f(q)^{P_{k}-P_{k-1}},P_{k}为第k个素数

我们有P_{k}-P_{k-1}=O(\ln n)

预处理出f(q)^0,f(q)^1,\dots,f(q)^{\ln\frac{n}{q}}

时间复杂度为O(\ln\frac{n}{q})

\sum\limits_{i=1}^n \ln\frac{n}{i}=n\ln n-\sum\limits_{i=1}^n \ln i=O(n)

总时间复杂度为O(n)

注意到该做法与模数无关，于是一个毒瘤的想法产生了（

Part3.

给定 f(n),g(n) 其中f(n)为积性函数

求h(n)=\sum\limits_{d|n}f(d)g(\frac{n}{d})

h(n)\leftarrow g(n)

考虑埃氏筛

h(p_{1}^{\alpha_{1}}\dots p_{k}^{\alpha_{k}})\leftarrow\sum\limits_{i_{j}=0}^{\alpha_{j}}f(p_{j}^{i_{j}})h(\dfrac{n}{{p_{j}}^{i_{j}}})

证明不难留给读者当做习题

时间复杂度O(\sum\frac{n}{p^k})=O(n\ln \ln n)