数论函数学习笔记

我真的好想你

在每一个雨季

你选择遗忘的

是我最不舍的

如果发现本文有任何错误，欢迎留言指正或者联系 920861971@qq.com

tls的博客!

jls的博客!

莫比乌斯函数学习笔记

学军巨佬的博客

OI-WIKI-Mobius

nanoape的博客！

前前置：

引入两个概念：

卷积：Convolution

是通过两个函数 $f$ 和 $g$ 生成第三个函数的一种数学算子。wiki

反演：Inversion

假设有两个函数$f$ 和 $g$ 满足:

$$f(n) = \sum_k a_{n,k} \ g(k)$$

已知 $g$ 求 $f$ 还是很水的。已知 $f$ 求$g$ 的过程称为反演。
现在反演一波（乱写），此处可以跳到前置：整除分块  很杂乱而且不是很清晰。

二项式反演：

$$f(n)=\sum_{k=0}^n\binom nkg(k)$$ $$g(n)=\sum_{k=0}^n(-1)^{n-k}\binom nkf(k)$$

前置：整除分块

引入：

整除分块是用来处理形如$\sum_{i=1}^n\lfloor \frac{n}{i}\rfloor$
的式子的方法。
当数据加强到$10^{10}$以上时，我们需要低于$O(n)$的更优秀的解法。
通过打表或者理性感知，我们可以发现，对于某些$\lfloor \frac{n}{i}\rfloor$，他们的值是相同的，并且呈块状分布。
由前任的经验，或者自己打表，发现对于一个块，假设它的起始位置的下标为 $l$ ，那么可以得到的是，它的结束位置的下标为 $\lfloor\frac{n}{\lfloor\frac{n}{l}\rfloor}\rfloor$
再写程序时候，要注意除法除0的情况，一般是会判断一下n/l的。

//求\sum_{i=1}^n n/i 
//枚举左端点和右端点，右端点n/(n/l)
//右端点要想清楚，注意除数除0的情况，一般是会判断一下n/l的。
for(int l=1,r;l<=n;l=r+1){
    r=n/(n/l);
    ans+=(n/l)*(r-l+1);
}

//如果求\sum_{i=1}^n n/i A[i]
//树状数组访问前缀和。
for(int l = 1; l <= n; l = r+1){
    r = n / (n/l);
    ans += query(n/l)*(r-l+1);
}

一些题目

1. bzoj1257整除分块

   题意：

   给定n，k。求$\sum_{i=1}^{n} k \ mod\ i。$

   思路：

   首先有$k \bmod i = k - \lfloor \frac{k}{i}\rfloor*i$

原式等价于求 $n*k-\sum_{i=1}^{n}( \lfloor \frac{k}{i}\rfloor \times i)$

对于每个区间的 $(l,r)$ ，等差数列搞一搞，得到公式为 $(k/l)\times (r-l+1) \times (l+r)/2$

1. P2424 约数和

   题意：

   $f(x)=\sum{d|x} d$  求$\sum{i=X}^Y f(i)$

思路：

首先想到前缀和。$1\rightarrow y$ 的 减去 $1 \rightarrow (x-1)$ 的。
那么在$1 \rightarrow n$中会出现的约数显然有n个（即1→n每个数都可作为约数），则对于约数 $d,d\in [1,n]$ ，其对约数和的贡献为$ d\times \lfloor n/d \rfloor$，即$ans=\sum_{i=1}^n(i\times\lfloor \frac{n}{i}\rfloor)$。

然后对于$(i\times\lfloor \frac{n}{i}\rfloor)$直接数论分块套上等差数列求和就好了。
$s=(n/l)\times (l+r)\times(r-l+1)/2;$

1. loj124除数函数求和1

题意：

给定$1\le n,k\le 1e7$，求$\sum{i=1}^n\sum{d|n}d^k \ mod \ 1e9+7$的值

思路：

$\sum{i=1}^n\sum{d|n}d^k = \sum_{i=1}^n(i^k\times \lfloor \frac{n}{i} \rfloor)$   $\because i^k$不同 所以不能数论分块。观察到数据范围，叉掉$n \ logn$做法，考虑线性筛。
令$f(i) = i ^ k$,不难发现这个是积性函数。于是有$f(a\cdot b)=f(a)\cdot f(b)$线性筛递推，$O(n)$复杂度。

1. P2260 [清华集训2012]模积和

题意：

$\sum{i=1}^n\sum{j=1}^m(n \ mod \ i) \times (m \ mod \ j), i\neq j \ mod\ 19940417$的值。

思路：

• 做这种题，看到不熟悉的模数，先看看他是不是质数，能不能因式分解。发现$19940417 = 7 \times 2848631$。不管有没有用 ，都先分解出来。
• 开始推式子：先不管$i\neq j$的条件。

原式 $= \sum{i=1}^n(n-i\cdot \lfloor n/i\rfloor) \sum{j=1}^m(m-j\times\lfloor m/j\rfloor)=(n^2-\sum{i=1}^n(i\times\lfloor n/i\rfloor))(m^2-\sum{j=1}^m(j\times\lfloor m/j\rfloor))$

老套路分块等差数列求和 ，这一步可以解决

• 下面考虑$i == j$的情况，

$jianqu = \sum{i=1}^{min(n,m)}(n-i\times\lfloor n/i\rfloor)\times(m-i\times\lfloor m/i\rfloor) = \sum{i=1}^{min(n,m)}(n\times m+i^2\times\lfloor n/i\times m/i\rfloor-n\times i\times \lfloor m/ i \rfloor - m\times i\times \lfloor n/ i \rfloor )$

对于$n\times m $ 累加，对于$n\times i\times \lfloor m/i\rfloor $和$m\times i\times \lfloor n/i\rfloor $ 还是老套路，数论分块套等差数列。
对于比较难求的 $i^2\times \lfloor n/i \times m/i \rfloor$此时应用平方求和公式$1^2+2^2+……+n^2=\frac{n(n+1)(2n+1)}{6}$前缀搞一搞就行了

• 这道题取模，发现6与模数互质，ex_gcd 求一下逆元。

  参考代码

1. bzoj1257参考代码

2. 洛谷P2424参考代码

3. loj124除数函数求和1

4. P2260 [清华集训2012]模积和

   数论函数基础知识

   几个定义

• 数论函数:定义域为正整数的函数。（没特殊提及情况下以下函数均为数论函数）
• 积性函数:如果a,b满足$gcd(a,b) = 1$;则有$f(ab) = f(a)(b)$
• 完全积性函数:$\forall a,b$ ，满足$f(ab) = f(a)(b)$

  几个性质和例子

1. 欧拉函数:$\varphi(n) = \sum_{i=1}^n[gcd(i,n)==1]$，是积性函数。
2. 莫比乌斯函数：$\mu$,当n有平方因子的时候，$\mu(n)=0$，否则设 $n$ 为 $k$ 个不同质因子的乘积。$\mu(n) = (-1)^k$。
3. 除数函数:这不是完全积性函数，$\sigmaa n = \sum{d|n} d^a$。其中$d(n) = \sigma_0{n}$为n的因数个数，$\sigma_1(n) = \sigma(n)$为$n$的约数之和。
4. 幂函数:完全积性函数。$id_k(n)$,表示$n^k$
5. 单位函数:完全积性函数。$e(n) = [n = 1]$

$$\sum_{d|n}\mu(d)= \begin{cases} 1, & \text{ $n=1$ } \\ 0, & \text{ $n\gt1$} \end{cases}$$

Dirichlet卷积

定义：

函数$f$与$g$的Dirichlet卷积定义如下：

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

等价于

$$(f*g)(n) = \sum_{i*j = n}f(i)\times g(j)$$

类似的，不难得出

$$(f*g*h)(n)=\sum_{i*j*k=n}f(i)\times g(j) \times h(k)$$

性质:

• 交换律，结合律：略
• 分配律：$f(g+h)=fg+g*h$
  证明如下： $$(g+h)\times f=\sum_{d|n}(g(d)+h(d))f(\frac{n}{d}) \\=\sum_{d|n}g(d)f(\frac{n}{d})+\sum_{d|n}h(d)f(\frac{n}{d}) \\=g\times f+h\times f$$

• 单位元：$f*e=f$
  证明如下：

  $$(f\times e)(n)=\sum_{d|n}f(d)e(\frac{n}{d})\\=\sum_{d|n}f(d)[\frac{n}{d}==1]\\=\sum_{d|n}f(d)[n==d]=f(n)$$

• 如果$f,g$都为积性函数，那么$f*g$也是积性函数。
  证明如下：

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

  对于$h$，有

  $$h(x)h(y)=(\sum_{d_1|x}f(d_1)g(\frac{x}{d_1}))(\sum_{d_2|y}f(d_2)g(\frac{y}{d_2})) \\=\sum_{d_1|x,d_2|y}f(d_1d_2)g(\frac{xy}{d_1d_2})\\=\sum_{d|xy}f(d)g(\frac{xy}{d})=h(xy)$$

对于任意一个函数$f$,则一定存在一个函数$g$满足$f*g=e$,则$g$叫做$f$的Dirichlet逆。

计算Dirichlet卷积

设$h=f*g$
计算$h(n)$:根据定义，枚举因数，时间复杂度为$O(\sqrt n)$

h(n)=0;
for (int i=1;i*i<=n;i++){
    if (n%i)
        continue;
    h(n)+=f(i)*g(n/i);
    if (i*i!=n)
        h(n)+=f(n/i)*g(i);
}
```  
计算$h$，其中h的定义域为1~n,类似筛法，不难得到$O(n\ log\ n)$
```cpp
memset(h,0,sizeof h);
for (int i=1;i<=n;i++)
    for (int j=1;i*j<=n;j++)
        h(i*j)+=f(i)*g(j);

几个Dirichlet卷积

• 除数函数卷上1。$(1 = id_0)$

$$d(n) = \sum_{d|n}1\Rightarrow d = 1*1$$ $$\sigma(n)=\sum_{d|n}d\Rightarrow \sigma=id*1$$

• 莫比乌斯函数与1的卷积：很重要!
  其中 $k$ 为 $n$ 不同种类的质因数个数。
  $\sum{d|n}\mu(n)=\sum{i=0}^{k}(-1)^i\times \binom{k}{i}=(1-1)^{k}=0^{k}$
  其中，对于$0^0$没有定义，考虑到$k = 0$的只有$n = 1$,而$\mu (1) = 1$，所以有

$\sum_{d|n}\mu(n)=[n=1]=e(n)$ [P]表示P成立时候为1，否则为0。

所以就会有:$e = \mu * 1 $  这里可以看出 $\mu$ 和 $1$在Dirichlet卷积的意义下互为逆元。记住这个式子！！这个对于莫比乌斯反演非常非常非常的重要！！！

• 常用的卷积： $$\varphi*1=??$$ 考虑到，若d为n的因数，则$φ(d)$即与n的最大公约数为$\frac{n}{d}$的数的个数。所以： $$\sum_{d|n}\varphi(d)=n \quad \Longrightarrow \varphi*1=id$$
• 关于幂函数 $$id_k\times(a*b)=(id_k\times a)*(id_k\times b)$$ $$(\varphi\times id_k)*id_k=id_{k+1}$$

莫比乌斯反演

一些题目

1. bzoj1101Zap反演经典题目

   题意：

思路：

1. gym101982Coprime Integers

   题意:

   思路:

2. P5572 [CmdOI2019]简单的数论题

   参考代码

3. 2015SDOI约数个数和

   题意：

   思路：

   参考代码：

   分块的预处理（慢一些）
   优化预处理d

杜教筛

利用Dirichlet卷积来构造递推式，从而对一些数论函数进行快速求和的方法。

杜教筛不像是传统的筛法（雾）

例子：

快速求$$

洲阁筛

MIN_25筛

一些阅读资料

我可能有些一些也没读过…(羞愧.jpg)
炫酷反演魔术 —VFleaKing