【学习笔记】数论

前言

lyc 买了洛谷网校 - 省选基础

但是她发现每次听了数论课之后过了一会就会忘掉

于是她写了一篇学习笔记

【持续更新】
upd：鸽了

数论函数

定义域为正整数、值域为复数的自己的函数称为 数论函数。

积性函数

设 $f$ 为数论函数且当 $\gcd(a,b)=1$ 时，有 $f(a)\times f(b)=f(a \times b)$ ，则称 $f$ 为积性函数

容易看出，对于任何积性函数有 $f(1)=1$

特别的，若数论函数 $f$ 对于任何 $a,b$ 都有 $f(a)\times f(b)=f(a\times b)$ ，则称 $f$ 为完全积性函数。

容易看出，若 $f$ 为积性函数，且 $n={p_1}^{a_1}{p_2}^{a_2}\dots{p_s}^{a_s}$ 是 $n$ 的标准分解，则有

$f(n)=f({p_1}^{a_1})f({p_2}^{a_2})\dots f({p_s}^{a_s})$

利用上式，大部分积性函数可以用欧拉筛进行求值

线性筛（欧拉筛）

这个 lyc 至少还记得住（

一些有用的函数

单位函数（或者是元函数之类的东西，不太清楚qwqwq） $\epsilon$ 的定义为 $\epsilon (n)=[n=1]$

这里 $[\ ]$ 的含义为：若 $[\ ]$ 内的条件为真则为 $1$ ，否则为 $0$

显然，单位函数是积性函数

除数函数 $\sigma_k(n)$ 表示 $n$ 的因子的 $k$ 次方之和

形式化的， $\sigma_k(n)=\sum\limits_{d|n}d^k$

$n$ 的约数个数 $\sigma_0(n)$ 常记为 $d(n)$ ，约数和 $\sigma_1(n)$ 常记为 $\sigma(n)$

除数函数是积性函数

幂函数 $Id_k(n)=n^k$ ， $Id=Id_1$

一般的，$1$ 表示取值恒为 $1$ 的常函数

欧拉函数

定义

欧拉函数 $\varphi(n)$ 表示不超过 $n$ 且与 $n$ 互质的整数个数。

形式化的， $\varphi(n)=\sum\limits_{i=1}^{n}[\gcd(i,n)=1]$

欧拉函数是积性函数。

计算

通过容斥原理可以得到

$\varphi (n)=n\prod\limits_{i=1}^{s} (1- \frac{1}{p_1})$

其中 $n={p_1}^{a_1}{p_2}^{a_2}\dots{p_s}^{a_s}$ 是 $n$ 的标准分解

时间复杂度 $\mathcal{O(\sqrt{n})}$

int phi(int x){
	int ans=x;
	for (int i=2;i*i<=x;i++){
		if (x%i==0){
			ans=ans/i*(i-1);
			while (x%i==0) x/=i;
		}
	}
	if (x>1) ans=ans/x*(x-1);
	return ans;
}

可以利用 欧拉筛 在 $\mathcal{O(n)}$ 的时间内计算 $\varphi$ 在 $1$ 到 $n$ 处的取值

memset(prime,true,sizeof(prime));
prime[0]=prime[1]=false;
sum[1]=phi[1]=1;

for (int i=2;i<=MAXN;i++){
	if (prime[i]){
		primes[++tot]=i;
		phi[i]=i-1;
	}

	for (int j=1;j<=tot&&primes[j]*i<=MAXN;j++){
		prime[i*primes[j]]=false;
		if (i%primes[j]==0){
			phi[i*primes[j]]=phi[i]*primes[j];
			break;
		}
		else phi[i*primes[j]]=phi[i]*(primes[j]-1);
	}
}

性质

对于任意 $n$ ，有

$n=\sum\limits_{d|n}\varphi(d)$

数论分块

是非常常用的东西 所以有必要讲一讲

数论分块适用于这样的形式：

$\sum\limits_{i=1}^{n} \left\lfloor \frac{n}{i} \right\rfloor$

我们发现有许多的 $\left\lfloor \frac{n}{i} \right\rfloor$ 值是相同的，相同的值形成了一个个连续的块，所以可以用数论分块来加速求和过程，复杂度 $\mathcal{O(\sqrt{n})}$ 。

附代码

for(int l=1,r;l<=n;l=r+1){
	r=n/(n/l);
	ans+=(r-l+1)*(n/l);
}

其中 ans+=(r-l+1)*(n/l); 的意义为 有长度为 r-l+1 的块的值为 n\l 。

顺带一提，这个式子可以化为

$\sum\limits_{i=1}^{n} \left\lfloor \frac{n}{i} \right\rfloor = \sum\limits_{k=1}^{n}d(k)$

这里 $d(k)$ 是前文提到过的表示约数个数的函数

由于 $d$ 可以用欧拉筛预处理出来，而这个式子就是 $d$ 的前缀和，所以可以在线性时间内预处理出来。

当然，并不是所有可以用数论分块解决的问题都可以这样在线性时间内预处理（比如在求和的时候乘个什么东西 是很常见的形式），这就是数论分块的意义所在。

Dirichlet 卷积

定义

设 $f,g$ 是数论函数，且数论函数 $h$ 满足

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

则称 $h$ 为 $f,g$ 的 Dirichlet 卷积， 记作 $h=f*g$

性质

对于任意数论函数 $f$ ，有 $f = f * \epsilon = \epsilon * f$ ，即单位函数 $\epsilon$ 是 Dirichlet 卷积的 单位元。

Dirichlet 卷积满足 交换律和结合律

若 $f,g$ 为积性函数，则 $h=f * g$ 也是积性函数

应用

除数函数的定义可以写成

$\sigma_k= 1 * Id_k$

欧拉函数的性质可以写成

$Id=\varphi * 1$

Mobius 函数

莫比乌斯函数 $\mu(n)$ 的定义为

$\mu(n)= \begin{cases} 1&n=1\\ (-1)^s&n=p_1 p_2 \dots p_s\\ 0&\text{otherwise} \end{cases}$

其中 $p_1 , p_2 \dots p_s$ 为不同的质数

容易看出， $\mu(n)$ 在 $n$ 无平方因子时非 $0$ 。

$\mu$ 是 积性函数

非常非常重要的性质

对于任意正整数 $n$ ，有

$\sum\limits_{d|n}\mu(d)=\epsilon (n)$

写成狄利克雷卷积的形式即为

$\mu * 1=\epsilon$

Proof:

$n=1$ 时显然。

若 $n > 1$，设 $n$ 有 $s$ 个不同的素因子，由于 $\mu(d) \ne 0$ （这里不等号渲染有莫名其妙的锅）当且仅当 $d$ 无平方因子，故 $d$ 中每个素因子的指数只能为 $0$ 或 $1$。故有

$\sum\limits_{d|n}\mu(d)=\sum\limits_{i=0}^{s}(-1)^i \dbinom{s}{i}=\sum\limits_{i=0}^{s}1^{s-i}(-1)^i \dbinom{s}{i}=(1-1)^s=0$

（第三步使用了 二项式定理 ）

Mobius 变换

我们有数论函数 $f$ ，定义数论函数 $g$ 。若

$g(n)=\sum\limits_{d|n}f(d)$

则称 $g$ 为 $f$ 的 Mobius 变换 ，$f$ 为 $g$ 的Mobius 逆变换。

写成 Dirichlet 卷积 的形式即为 $g=f * 1$

Mobius 反演定理

Mobius 反演定理 指出，上式的充要条件为

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

写成 Dirichlet 卷积 形式即为 $f=g*\mu$

Proof:

把 $\mu$ 的定义代进去就证出来了（

可是我们有更优美的证明方法

$f = f * \epsilon = f * 1 * \mu = g * \mu$

关于解题

首先我们来看一道题。

求二元组 $(x,y)$ 的个数，满足 $1\le x\le n, 1\le y \le m$ 且 $x,y$ 互质

$n,m \le 10^7$ ，多测。

显然，答案为

$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} [\gcd(i,j)=1]$

进行转化

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

（第二步使用了 Mobius 函数的性质 $\mu * 1 = \epsilon$）

然后这个式子可以通过预处理 $\mu$ ，然后数论分块在 $\mathcal{O(\sqrt n)}$ 时间内求出

Q：就这？

Q：这就是莫比乌斯反演嘛，i了i了

Q：那你之前提到的 Mobius 反演定理 和 Mobius 变换 是干啥的？

A：之后填坑（（（