进阶数论

· · 算法·理论

相较初等数论而言，更加高级。

莫比乌斯反演

简介：

f(n)=\sum\limits_{d|n}g(d)\Leftrightarrow g(n)=\sum\limits_{d|n}\mu(d)f(\frac{n}{d})

其中 \mu 是莫比乌斯函数。

\begin{cases} 1&n=1\vee\texttt{n的不同质因子个数为偶}\\ -1&\texttt{n的不同质因子个数为奇}\\ 0&\exists x,x^2|n \end{cases}

证明：容易发现左式表明 f 是 g 与 1 的迪利克雷卷积，我们只需证明 \mu * 1=\epsilon 即可。

(\mu * 1)(i)=\sum\limits_{d|i}\mu(d)=\sum\limits_{i=0}^kC_k^i(-1)^i=\begin{cases}1(i=1)\\0(i\not=1)\end{cases}=\epsilon(i)

其中 k 是 i 本质不同的质因子个数。

数论分块

根号科技 是个好东西。

数论分块，顾名思义一种数论中的分块，通常处理形如 \sum\limits_{i=1}^nf(i)\times\left\lfloor\dfrac{k}{i}\right\rfloor 的和式。

对于形如 \sum\limits_{i=1}^k\left\lfloor\dfrac{n}{i}\right\rfloor 的式子，容易发现如果 n<i，结果为 0，对答案没有任何贡献。所以我们只需统计对于 i\in[1,\min(k,n)] 的情况即可。方便起见，先讨论对于 [1,n] 的情况。

首先，回想我们求因数个数的代码，枚举 i=\overline{1,2,\cdots,\sqrt{n}}，为什么呢？

对于 \forall a,b\in\mathbb{N^* }\wedge ab=n\wedge a\le b，必定有 a\le\sqrt{n}（a^2\le ab=n），所以 n 最多只有 2\sqrt{n} 个因数。即 \left\lfloor\dfrac{n}{i}\right\rfloor,i=\overline{1,2,\cdots,n} 最多只有 2\sqrt{n} 个取值。

二项式反演

反演，用二项式，就这样。

若有

g(n)=\sum\limits_{i=0}^n\left(^n_{i}\right)f(i)

题目

[x=1]=\sum\limits_{d|x}\mu(d) \sum\limits_{d|n}\mu(\frac nd)d=\varphi(n) \sum\limits_{d|n}\varphi(d)=n d(xy)=\sum\limits_{i|x}\sum\limits_{j|y}\left[(x,y)=1\right] \varphi(xy)=\varphi(i)\varphi(j)\prod\limits_{p\in\operatorname{Prime}\wedge p\mid(i,j)}\frac{p}{p-1}

大部分的题只需用上述几个式子转化，化简，再配合上数论分块以及杜教筛即可。

P1390 公约数的和

求 \sum\limits_{i = 1}^n \sum\limits_{j = i + 1}^n \gcd(i, j)。

\begin{array}{c} &\sum\limits_{i = 1}^n \sum\limits_{j = i + 1}^n \gcd(i, j)\\ =&\sum\limits_{k=1}^n\varphi(k)\dfrac{\left\lfloor\dfrac{n}{k}\right\rfloor\left(\left\lfloor\dfrac{n}{k}\right\rfloor -1\right)}{2} \end{array}

暴力即可，无需优化。

P1447 [NOI2010] 能量采集

求 \sum\limits_{i = 1}^n \sum\limits_{j =1}^m [2\gcd(i, j)-1]。

令 n\le m。

\begin{array}{c} &\sum\limits_{i = 1}^n \sum\limits_{j =1}^m [2\gcd(i, j)-1]\\ =&\left[2\sum\limits_{k=1}^n\varphi(k)\left\lfloor\dfrac{n}{k}\right\rfloor\left\lfloor\dfrac{m}{k}\right\rfloor\right]-nm \end{array}

同样，筛完 \varphi 暴力就可以。

P1829 [国家集训队] Crash的数字表格 / JZPTAB

求 \sum\limits_{i = 1}^n \sum\limits_{j =1}^m \operatorname{lcm}(i,j)。

令 n\le m。

\begin{array}{c} &\sum\limits_{i = 1}^n \sum\limits_{j =1}^m \operatorname{lcm}(i,j)\\ =&\sum\limits_{i = 1}^n \sum\limits_{j =1}^m\dfrac{ij}{\gcd(i,j)}\\ =&\sum\limits_{k=1}^n\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}ijk[\gcd(i,j)=1] \end{array}

[MtOI2019] 幽灵乐团

好题，很好的题，做了两个晚自习。

容易发现，原式等于 \prod\limits_{i=1}^a\prod\limits_{j=1}^b\prod\limits_{k=1}^c\left(\dfrac{ij}{\gcd(i,j)\gcd(i,k)}\right)^{f(type)}。

拆成 \prod\limits_{i=1}^a\prod\limits_{j=1}^b\prod\limits_{k=1}^c\left({ij}\right)^{f(type)}，\prod\limits_{i=1}^a\prod\limits_{j=1}^b\prod\limits_{k=1}^c\gcd(i,j)^{f(type)} 两个部分，分开求解。

\begin{array}{c} &\large{type0}\\ &\prod\limits_{i=1}^a\prod\limits_{j=1}^b\prod\limits_{k=1}^c\left({ij}\right)\\ =&\prod\limits_{i=1}^ai^{bc}\times\prod\limits_{i=1}^bi^{ac}\\ =&(a!)^{bc}(b!)^{ac}\\\\ &\prod\limits_{i=1}^a\prod\limits_{j=1}^b\prod\limits_{k=1}^c\gcd(i,j)\\ =&\left[\prod\limits_{t=1}^{\min(a,b)}\prod\limits_{i=1}^{}\right]^c \end{array}