数论学习笔记

前言

该从哪写起呢。

积性函数

定义不再赘述。

常见的 $\varphi$ $\mu$ $\sigma_0$ $\sigma_1$都是积性函数。

其中$\sigma_0$为约数个数和。 $\sigma_1$为约数和。

$\mu$的定义为

\mu(n)=\left\{ \begin{array}{**lr**} 1 & & n=1\\ (-1)^s & & n=p_1p_2...p_s \\ 0 & & otherwise \end{array} \right.

在存在平方因子时$\mu$为 $0$

Dirichlet 卷积

本篇中所有的卷积 $*$ 均为$Dirichlet$卷积。

定义为

$h(n)=\sum_{d|n}f(d)g(\frac{d}{n})$

称 $h$ 为 $f$ 和 $g$ 的卷积。

大概有一些显而易见的卷积恒等式，如

$\begin{aligned} Id&=\varphi * 1\\ \epsilon&=\mu*1 \end{aligned}$

第二个其实是 $\mu$ 的定义式。

莫比乌斯反演

莫比乌斯反演指

$\begin{aligned} f&=g*1\\ g&=f*\mu \end{aligned}$

不难发现，函数 $1$ 也代表着将原函数做高维前缀和。

这与生成函数中的全 $1$ 生成函数不谋而合。

证明根据定义。

$\begin{aligned} g&=g*\epsilon\\ &=g*1*\mu\\ &=f*\mu \end{aligned}$

常用的形式为将 $[gcd(x,y)=1]$ 改写为$\sum_{d|gcd(i,j)}\mu(d)$

证明根据定义。

$\begin{aligned} \left[gcd(x,y)=1\right]&=\epsilon(gcd(x,y))\\ &=\mu*1 \end{aligned}$

题目

YY的GCD

求

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

先整个简单的。

$\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=1]\\ =&\sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)}\mu(d)\\ =&\sum_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor \end{aligned}$

除法分块。

那就在上面的经典题外面枚举一个 $p$

$\begin{aligned} &\sum_{p}\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=p]\\ =&\sum_p\sum_{d=1}^{\min(n,m)}\mu(d)\left\lfloor\frac{n}{dp}\right\rfloor\left\lfloor\dfrac{m}{dp}\right\rfloor \end{aligned}$

我们还是希望预处理那个前缀和。 换元一下

$\begin{aligned} &\sum_{t=1}^{\min(n,m)}\sum_{p|t}\mu(\frac{t}{p})\left\lfloor\frac{n}{t}\right\rfloor\left\lfloor\dfrac{m}{t}\right\rfloor\\ =&\sum_{t=1}^{\min(n,m)}f(t)\left\lfloor\frac{n}{t}\right\rfloor\left\lfloor\dfrac{m}{t}\right\rfloor\\ \end{aligned}$

我们依然可以预处理 $f$ ，复杂度为 埃筛的复杂度 $O(nloglogn)$

公约数的和

大概不是莫反的题。

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

考虑求

$\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)\\ =&\sum_{d=1}^nd\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=d]\\ =&\sum_{d=1}^nd\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{n}{d}}[gcd(i,j)=1]\\ =&\sum_{d=1}^nd(2\sum_{i=1}^{\frac{n}{d}}\varphi(i)-1) \end{aligned}$

你发现他们长得都一样。

Product

再写一遍罢。

$\begin{aligned} &\prod_{i=1}^n\prod_{j=1}^n\frac{lcm(i,j)}{gcd(i,j)}\\ =&\prod_{i=1}^n\prod_{j=1}^n\frac{i\times j}{gcd^2(i,j)} \end{aligned}$

分子随便算。

考虑求

$\begin{aligned} &\prod_{i=1}^n\prod_{j=1}^ngcd(i,j)\\ =&\prod_{d=1}^nd\prod_{i=1}^n\prod_{j=1}^n[gcd(i,j)=d]\\ =&\prod_{d=1}^nd^{\sum_{i=1}^{\frac{n}{d}}{\sum_{j=1}^{\frac{n}{d}}}[gcd(i,j)=1]} \\ =&\prod_{d=1}^nd^{2{\sum_{i=1}^{\frac{n}{d}}\varphi(i)-1}} \end{aligned}$

你发现他们好像确实一样。

约数个数和

求

$\sum_{i=1}^n\sum_{j=1}^m\sigma_0(i\times j)$

推

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

你发现好像确确确实没啥区别。

对于最后一个式子考虑贡献。考虑每个数在$n$内的倍数会出现即可。

数字表格

求

$\prod_{i=1}^n\prod_{j=1}^mf_{gcd(i,j)}$

既

$\begin{aligned} &\prod_{i=1}^n\prod_{j=1}^m\prod_{d|i,d|j}f(d)[gcd(i,j)=d]\\ =&\prod_{d=1}^nf(d)^{\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[gcd(i,j)]=1} \end{aligned}$

看指数很对味对吧。

$\begin{aligned} &\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[gcd(i,j)=1]\\ =&\sum_{p=1}^\frac{n}{d}\mu(p)\frac{n}{dp}\frac{m}{dp} \end{aligned}$

枚举 $T = dp$ 就可以有

$\prod_{T=1}^n (\prod_{k|T}f(k)^{\mu(\frac{T}{k})})^{\frac{n}{T}\frac{m}{T}}$

括号里面那个调和级数预处理前缀和即可。

$\sum_{p=1}^{\frac{n}{d}}\mu(p)\frac{n}{dp}\frac{m}{dp}$

最小公倍数之和

求

$\sum_{i=1}^n\sum_{j=1}^nlcm(a_i,a_j)$

只需要对每个数字单独统计贡献即可。

即求

$\sum_{i=1}^n\sum_{j=1}^nlcm(i,j)\times c_i\times c_j$

其中 $c_i$ 即为 数字 $i$ 出现的次数。

剩下的就是莫比乌斯反演非常基础的一些操作了。

$\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^n\frac{i\times j}{\gcd(i,j)}\times c_i \times c_j\\ =&\sum_{i=1}^n\sum_{j=1}^n\sum_{d|i,d|j}[gcd(i,j)=d]\frac{i\times j}{d}\times c_i \times c_j\\ =&\sum_{d=1}^n\sum_{i=1}^\frac{n}{d}\sum_{j=1}^\frac{n}{d}[gcd(i,j)=1]i \times j \times d\times c_{id} \times c_{jd}\\ =&\sum_{d=1}^n\sum_{k=1}^\frac{n}{d}\sum_{i=1}^\frac{n}{dk}\sum_{j=1}^\frac{n}{dk}\mu(k) \times k^2 \times i\times j \times c_{idk} \times c_{jdk}\\ =&\sum_{d=1}^ndk\sum_{k=1}^\frac{n}{d}\mu(k)\times k(\sum_{i=1}^\frac{n}{dk}i\times c_{idk})^2\\ =&\sum_{T=1}^nT(\sum_{k|T}\mu(k)\times k)(\sum_{i=1}^\frac{n}{T}i\times c_{iT})^2 \end{aligned}$

于神之怒

Youwike の 怒 😡

求

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

其中 $k$ 给定。

先推推试试嘛。

$\begin{aligned} &\sum_{d=1}^nd^k\sum_{j=1}^\frac{n}{d}\sum_{j=1}^\frac{m}{d}\sum_{f|i,f|j}\mu(f)\\ =&\sum_{d=1}^nd^k\sum_{f=1}^\frac{n}{d}\mu(f) \lfloor\frac{n}{df}\rfloor\lfloor\frac{m}{df}\rfloor\\ =&\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor(\sum_{d|T}\mu(\frac{T}{d})\times d^k)\\ =&\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor F(T) \end{aligned}$

可以体会其中枚举约数，枚举倍数的转化。

发现后面就是就是 $\mu * idk$。

由于这两个都是积性函数，因此 $F$ 也是积性函数。

那么有

$\begin{aligned} &f(T)=\prod_{i=1}^tf(p_i^{x_i})\\ &f(p_i^{x_i})=\sum_{d|p_i^{x_i}}\mu(\frac{p_i^{x_i}}{d})idk(d) \end{aligned}$

对于 $\mu$ 显然只有两种情况是没有平方因子的。

即

$\begin{aligned} &f(p_i^{x_i})=idk(p_i^{x_i})-idk(p_i^{x_i-1})\\ =&(p_i^{k}-1)\times p_i^{k\times (x_i-1)} \end{aligned}$

写出来发现

$f(p_i^{x_i})=f(p_i^{x_i-1})*idk(p_i)$

就能够线性筛了。

杜教筛

一种用来快速计算数论函数前缀和的方法。

即求

$S(n)=\sum_{i=1}^nf(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}^ng(d)\sum_{i=1}^{\lfloor\dfrac{n}{d}\rfloor}f(i)\\ =&\sum_{d=1}^ng(d)S(\lfloor\dfrac{n}{d}\rfloor) \end{aligned}$

把需要用到的 $S(n)$ 即 $i = 1$ 的情况提取出来，就能得到。

$\begin{aligned} &g(1)S(n)=\sum_{d=1}^ng(d)S(\lfloor\dfrac{n}{d}\rfloor)-\sum_{d=2}^ng(d)S(\lfloor\dfrac{n}{d}\rfloor)\\ =&\sum_{i=1}^n(f*g)(i)-\sum_{d=2}^ng(d)S(\lfloor\dfrac{n}{d}\rfloor) \end{aligned}$

需要找到一个 $g$ 快速计算前面和后面。

后面记忆化递归，并且在线性筛能搜索到的范围内直接进行计算，复杂度就可以优化到$O(n^{\frac{2}{3}})$

对于常见的筛 $\mu$ 和 $\varphi$ 的前缀和

对于 $\mu$

我们选择 $\mu * 1 = \epsilon$ 其中可以快速地计算出 $\epsilon$ 的前缀和。

对于 $\varphi$

我们选择 $\varphi * 1 = id$ 其中可以快速的计算出 $id$ 的前缀和。