数论-JZTXT

数论

小知识复习

整除、质数、线性筛、 $gcd$ 、 $exgcd$ 、逆元、快速幂、费马小定理、（扩展）欧拉定理、卢卡斯定理、中国剩余定理、原根、常见数论函数……

给一张比较有用的表：

例

求 $g^{\sum_{d|n}\binom{n}{d}}\pmod{999911659}$

$n,g\le 10^9$

Solution

一道可以复习一些知识点的题目。

先使用欧拉定理，由于 $999911659$ 为质数，所以 $ans\equiv g^{\sum_{d|n}\binom{n}{d}\pmod{999911658}}\pmod{999911659}$ 。

我们只需要考虑如何求出指数，发现是一个组合数取模问题，我们想到了卢卡斯定理。

卢卡斯定理：$\binom{n}{m}\equiv\binom{n/p}{m/p}\binom{n\bmod p}{m \bmod p}\pmod{p}$ ，但要求 $p$ 是个小质数。但我们不想使用扩展卢卡斯定理，我们发现 $999911658=2\times 3\times 4697\times 35617$ ，这四个都是小质数，我们能不能拆成模这四个质数下的答案，最终再合并呢？

显然是可以的，我们可以使用中国剩余定理。我们最终是可以得到 $\sum_{d|n}\binom{n}{d}$ 分别模这四个质数时得到的结果，这就相当于是四个同余方程组，利用中国剩余定理合并即可。

最终我们求出了指数，最终的答案直接一个快速幂即可。

狄利克雷卷积

常见数论函数

在介绍狄利克雷卷积之前，我们先给出常见的几个数论函数。

单位函数：$\varepsilon(n)=[n=1]$

恒等函数：$Id_k(n)=n^k$ ，其中当 $k=1$ 时简写为 $Id(n)=n$

常数函数：$1(n)=1$

欧拉函数：$\varphi(n)=\sum_{i=1}^{n}[gcd(i,n)=1]$

莫比乌斯函数：

\[\mu(n)= \begin{cases} 1,&\text{n=1}\\ 0,&\text{n存在平方因子}\\ (-1)^{x},&\text{$n=p_1\times p_2\cdots\times p_x$} \end{cases} \]

以上前三个函数均为完全积性函数，后两个为积性函数。

狄利克雷卷积

对于两个数论函数 $f,g$ ，我们定义其狄利克雷卷积为：

\[(f*g)(x)=\sum_{ab=x}f(a)g(b) \]

也可以写成：

\[(f*g)(x)=\sum_{d|x}f(d)g(\frac{x}{d}) \]

狄利克雷卷积满足交换律、结合律、分配律。

根据狄利克雷卷积，我们就可以得到一些数论函数之间的关系：

任意函数与单位函数

\[(f*\varepsilon)(n)=\sum_{d|n}f(d)\varepsilon(\frac{n}{d})=f(n) \]

当 $\frac{n}{d}=1$ ，即 $d=n$ 时 $\varepsilon(\frac{n}{d})=1$ ，此时值为 $f(n)$ 。其实也就是 $f*\varepsilon=f$ ，所以我们也称 $\varepsilon$ 为狄利克雷卷积运算的单位元。

莫比乌斯函数与常数函数

\[(\mu*1)(n)=\sum_{d|n}\mu(d)1(\frac{n}{d})=\sum_{d|n}\mu(d)=\varepsilon(n) \]

这里就要先给出莫比乌斯函数的一个性质：$\sum_{d|n}\mu(d)=[n=1]$ 。简写成：$\mu*1=\varepsilon$ 。

常数函数与常数函数

\[(1*1)(n)=\sum_{d|n}1(d)1(\frac{n}{d})=\sum_{d|n}1=d(n) \]

其中 $d(n)$ 表示 $n$ 的约数个数。

莫比乌斯反演

我们先摆出两个公式：

\[g(n)=\sum_{d|n}f(d)\Leftrightarrow f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d})\\ g(n)=\sum_{n|N}f(N)\Leftrightarrow f(n)=\sum_{d|n}\mu(d)g(\frac{n}{d}) \]

这就是莫比乌斯反演的两个最常用公式。

而莫比乌斯反演的考察基本上就是化简各种各样的式子了。

例1

求 $\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)=d]$

$n,m\le 5e4,T\le 5e4$

Solution

$gcd(x,y)=d$ 比较难处理，我们把它转化成 $1$ 。

\[\begin{aligned} ans&=\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)=d]\\ &=\sum_{x=di}^{n}\sum_{y=dj}^{m}[gcd(i,j)=1]\\ &=\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor} [gcd(i,j)=1]\\ &=\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{x|gcd(i,j)}\mu(x) \end{aligned} \]

以下我们令 $nn=\lfloor\frac{n}{d}\rfloor,mm=\lfloor\frac{m}{d}\rfloor$ 。转化为枚举 $x$ 并将 $\mu(x)$ 提前，得到

\[\begin{aligned} ans&=\sum_{x=1}^{nn}\mu(x)\sum_{i=1}^{nn} \sum_{j=1}^{mm} [x|gcd(i,j)]\\ ans&=\sum_{x=1}^{nn}\mu(x)\sum_{i=1}^{\lfloor\frac{nn}{x}\rfloor} \sum_{j=1}^{\lfloor\frac{mm}{x}\rfloor} 1\\ &=\sum_{x=1}^{nn}\mu(x)\lfloor\frac{nn}{x}\rfloor\lfloor\frac{mm}{x}\rfloor \end{aligned} \]

线性筛预处理 $\mu$ ，后面直接整除分块即可。

变式1

求 $\sum_{x=a}^{n}\sum_{y=b}^{m}[gcd(x,y)=d]$

$a,b,n,m\le 5e4,T\le 5e4$

Solution

二维前缀和转化一下即可，剩余的就和例1一样了。

变式2

求 $\sum_{k=1,k\in prime}^{n}\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)=k]$

$n,m\le 10^7,T\le 10^4$

Solution

按照例一的推式子方法，我们很容易得到：$\sum_{k=1,k\in prime}^{n} \sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}\mu(x)\lfloor\frac{n}{kx}\rfloor\lfloor\frac{m}{kx}\rfloor$ 。此时时间复杂度还是不够优秀，我们接着考虑如何降低时间复杂度。

我们设 $X=kx$ ，变为枚举 $X$ ，可以得到：

\[\sum_{X=1}^{n}\lfloor\frac{n}{X}\rfloor\lfloor\frac{m}{X}\rfloor\sum_{k|X,k\in prime}\mu(\frac{X}{k}) \]

我们发现后面那个东西是可以预处理的，我们枚举质数 $k$ ，对于它的所有倍数 $X$ 加上一个 $\mu(\frac{X}{k})$ 即可。再维护个前缀和和整除分块即可 $O(\sqrt n)$ 回答单次询问。

例2

求 $\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)$

$n\le 10^5$

Solution

显然枚举 $gcd$ ，可以得到：

\[\begin{aligned} ans&=\sum_{d=1}^{n}d\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)==d]\\ &=\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[gcd(i,j)==1] \end{aligned} \]

我们把目光聚集在后面的式子上，对于 $\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)=1]$ ，由于 $i,j$ 的上界都是 $n$ ，所以我们有更简便的方法。我们利用欧拉函数 $\varphi$ ，容易发现

\[\sum_{i=1}^{n}\sum_{j=1}^{i}[gcd(i,j)=1]=\sum_{i=1}^{n}\varphi(i) \]

所以 $\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)=1]=2\sum_{i=1}^{n}\varphi(i)-1$ ，减 $1$ 是减去 $(1,1)$ 的重复贡献。

所以直接预处理 $\varphi$ 的前缀和就可以直接做了。

例3

求 $\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$

$n,m\le 10^7$

Solution

\[\begin{aligned} ans&=\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)\\ &=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{gcd(i,j)}\\ &=\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]ij \end{aligned} \]

我们单独考虑计算后面的式子，仍然使用例一的套路：

\[\begin{aligned} s(n,m)&=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]ij\\ &=\sum_{d=1}^{n}d^2\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ij\\ &=\sum_{d=1}^{n}d^2\mu(d)\frac{\lfloor\frac{n}{d}\rfloor(\lfloor\frac{n}{d}\rfloor+1)}{2}\frac{\lfloor\frac{m}{d}\rfloor(\lfloor\frac{m}{d}\rfloor+1)}{2} \end{aligned} \]

预处理前面的前缀和，后面使用整除分块计算即可。

此时 $ans=\sum_{d=1}^{n}d\cdot s(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)$ ，再使用一次整除分块即可。

例4

设 $F_i$ 表示斐波那契数列的第 $i$ 项，求 $\prod_{i=1}^{n}\prod_{j=1}^{m}F_{gcd(i,j)}$ 对 $10^9+7$ 取模的结果。

$n,m\le 10^6,T\le 10^3$

Solution

仍然考虑去枚举 $gcd$ ，这个是比较经典的套路了

\[\begin{aligned} ans&=\prod_{d=1}^{n}\prod_{i=1}^{n}\prod_{j=1}^{m}[gcd(i,j)=d]F_d\\ &=\prod_{d=1}^{n}F_d^{\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=d]}\\ &=\prod_{d=1}^{n}F_d^{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]} \end{aligned} \]

我们单独考虑指数：

\[\begin{aligned} \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]&=\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\mu(x)\lfloor\frac{n}{xd}\rfloor\lfloor\frac{m}{xd}\rfloor \end{aligned} \]

此时已经可以利用两次整除分块做到单次 $O(n)$ 求解，但由于多测还是不行。所以我们继续，看到 $xd$ 这个东西，我们按照变式2，套路性地设为 $X$ 并进行枚举：

\[\begin{aligned} ans&=\prod_{X=1}^{n}(\prod_{d|X}F_d^{\mu(\frac{X}{d})})^{\lfloor\frac{n}{X}\rfloor\lfloor\frac{m}{X}\rfloor} \end{aligned} \]

注意指数上的加法转化为底数的乘法，指数上的乘法转变为幂，就可以得到上式了。

我们设 $G(x)=\prod_{d|x}F_d^{\mu(\frac{x}{d})}$ ，这个东西是可以通过枚举倍数以 $O(n \log n)$ 时间复杂度解决，并且可以维护前缀积。此时我们只需要一次整除分块即可，预处理出 $F$ ，$F$ 的逆元和 $G$ ，即可单次 $O(\sqrt n\log n)$ 解决。

例5

设 $d(x)$ 表示 $x$ 的约数个数，求：$\sum_{i=1}^{n}\sum_{j=1}^{m}d(i\cdot j)$

$T,n,m\le 5\times 10^4$

Solution

这里先给出一个结论：$d(i\cdot j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]$ ，证明咕了，可以当结论记。

\[ans=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}[gcd(x,y)=1] \]

转化成枚举约数：

\[\begin{aligned} ans&=\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)=1]\sum_{x|i}^{n}\sum_{j|y}^{m}1\\ &=\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)=1]\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\\ &=\sum_{d=1}^{n}\mu(d)\sum_{x=1}^{n}\sum_{y=1}^{m}[d|gcd(x,y)]\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\\ &=\sum_{d=1}^{n}\mu(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{xd}\rfloor\lfloor\frac{m}{yd}\rfloor\\ &=\sum_{d=1}^{n}\mu(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{xd}\rfloor\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{yd}\rfloor\\ \end{aligned} \]

此时预处理 $f(x)=\sum_{i=1}^{x}\lfloor\frac{x}{i}\rfloor$ ，利用整除分块即可单次 $O(\sqrt n)$ 回答询问。

杜教筛

杜教筛可以在亚线性时间内筛出积性函数的前缀和，当某些毒瘤出题人将数据范围开至无法使用线性筛，杜教筛有时是一个不错的选择。

假设我们此时要求积性函数 $f(x)$ 的前缀和，设 $S(x)=\sum_{i=1}^{x}f_i$ 。我们再找一个积性函数 $g$ ，利用狄利克雷卷积：

\[\begin{aligned} \sum_{i=1}^{n}(f*g)(i)&=\sum_{i=1}^{n}\sum_{d|i}f(d)g(\frac{i}{d})\\ &=\sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)\\ &=\sum_{d=1}^{n}g(d)S(\lfloor\frac{n}{d}\rfloor) \end{aligned} \]

我们考虑取 $d=1$ 得到 $g(1)S(n)$ ，对上面式子移项可以得到：

\[S(n)=g(1)S(n)=\sum_{i=1}^{n}(f*g)(i)-\sum_{i=2}^{n}g(i)S(\lfloor\frac{n}{i}\rfloor) \]

所以我们只需要找一个合适的积性函数 $g$ 使得可以快速算出 $\sum_{i=1}^{n}(f*g)(i)$ 和 $\sum_{i=1}^{n}g(i)$ ，就可以对第二项利用数论分块去递归求解 $S$ 。

如果直接使用杜教筛，时间复杂度约为 $O(n^{\frac{3}{4}})$ 。

如果我们先利用线性筛预处理出一些值，再使用杜教筛，值小的时候直接利用线性筛得到的值，杜教筛的时间复杂度可以做到最优，为 $O(n^{\frac{2}{3}})$ ，此时预处理出 $n^{\frac{2}{3}}$ 个值即可。

例1

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

Solution

显然可以考虑到 $\mu *1=\varepsilon$ ，我们取 $f=\mu,g=1$ 即可。其中 $g$ 的前缀和就是 $n$ ，$\varepsilon$ 的前缀和为 $1$ ，轻轻松松解决。

以 $\mu$ 为例给一份模板代码：

inline ll getmu(ll x)
{
    if(x<=N) return mu[x];
    if(Mu[x]) return Mu[x];
    ll ans=1;
    for(ll l=2,r;l<=x;l=r+1)
    {
        r=x/(x/l);
        ans-=(r-l+1)*getmu(x/l);
    }
    return Mu[x]=ans;
}

其中 $N$ 是线性筛预处理的最大值， $mu$ 是线性筛筛好的前缀和，$Mu$ 是记忆化数组。

例2

求 $\sum_{i=1}^{n}\varphi(i)$

Solution

考虑到 $\varphi*1=Id$ （证明在下方给出），我们取 $f=\varphi,g=1$ 即可。其中 $g$ 的前缀和为 $n$ ，$Id$ 的前缀和为 $\sum_{i=1}^{n}i=\frac{n(n+1)}{2}$ 。

再以 $\varphi$ 为例给一份模板代码：

inline ll getphi(ll x)
{
    if(x<=N) return phi[x];
    if(Phi[x]) return Phi[x];
    ll ans=(ll)x*(x+1)/2;
    for(ll l=2,r;l<=x;l=r+1)
    {
        r=x/(x/l);
        ans-=(r-l+1)*getphi(x/l);
    }
    return Phi[x]=ans;
}

考虑证明如上的式子，本质上就是证明：$\sum_{d|n}\varphi(d)=n$ 。

我们考虑将 $1$ 到 $n$ 分类，我们定义集合 $S_d=\lbrace x|1\le x\le n,gcd(x,n)=d\rbrace $ ，不难发现集合 $S_d$ 的元素形式为：$\lbrace x=kd|1\le k\le \frac{n}{d},gcd(k,\frac{n}{d}=1)$ ，因此集合 $S_d$ 中的元素个数为 $\varphi(\frac{n}{d})$ 。并且每个数仅属于一个集合，所以 $\sum_{d|n}\varphi(\frac{n}{d})=n$ ，即 $\sum_{d|n}\varphi(d)=n$ ，证毕。

例3

求 $\sum_{i=1}^{n}\varphi(i)\times i$

Solution

我们令 $f=\varphi\cdot Id,g=Id$ ，$(f*g)(n)=\sum_{d|n}\varphi(d)\times d\times \frac{n}{d}=n\times \sum_{d|n}\varphi(d)=n^2$ 。其中 $f*g$ 的前缀和为 $\sum_{i=1}^{n}i^2=\frac{n(n+1)(2n+1)}{6}$ 。

练习：[CQOI2015]选数

莫比乌斯反演+整除分块+杜教筛。

总结

杜教筛的核心就是选取好恰当的积性函数 $g$ ，使得 $g$ 的前缀和以及 $f*g$ 的前缀和都可以很方便计算。

题目来源（按照顺序给出）

例1：[SDOI2010]古代猪文

例1：[POI2007] ZAP-Queries

变式1：[HAOI2011] Problem b

变式2：YY的GCD

例2：GCD SUM

例3：[国家集训队] Crash的数字表格

例4：[SDOI2017] 数字表格

例5：[SDOI2015] 约数个数和

例1+例2：【模板】杜教筛