Part I 前置技能
数论分块
性质一:对于$\large \lfloor \frac Ni \rfloor$,最多只有$2\sqrt{N}$种取值
性质二:对于使得$\large \lfloor \frac N{i’} \rfloor$=$\large \lfloor \frac Ni \rfloor$的$i’$,
$i’{max}=\large \left \lfloor \frac N{\left \lfloor \frac Ni \right \rfloor } \right \rfloor$
$e.g.$求$\sum_{i=1}^N \lfloor \frac Ni \rfloor(N<10^{12})$
1 | for(l=1;l<=n;l=r+1){ |
2 | r=(n/(n/l)); |
3 | ans+=(n/l)*(r-l+1); |
4 | } |
【题意】:求$\sum_{i=1}^{n}{k\space mod\space i}$
$\sum_{i=1}^{n}{k\space mod\space i}$
$=\sum_{i=1}^{n}{k\space-\lfloor \frac{k}{i} \rfloori}$
$=n k-\sum_{i=1}^{n}{\lfloor \frac{k}{i}\rfloor*i}$
以这道题为例解释一下怎么做
对于同一个${\lfloor \frac{k}{i} \rfloor}$,设其区间为$[l,r]$
有$\sum_{i=l}^{r}{\lfloor \frac{k}{i} \rfloor}i \\
=\sum_{i=l}^{r}{\lfloor \frac{k}{i} \rfloor}\sum_{i=l}^{r}i$
1 | for(l=1;l<=n;l=r+1){ |
2 | r=(k/l)?min(k/(k/l),n):n; |
3 | ans+=(k/l)*Sum(l,r); |
4 | } |
$\sum_{i=1}^{n}\sum_{j=1 \land i \not = j}^{m}(n mod i)(m mod j)\\
=\sum_{i=1}^{n}\sum_{j=1}^{m}(n-{\left \lfloor \frac{n}{i} \right \rfloor}i)(m-{\left \lfloor \frac{m}{j} \right \rfloor}j)-\sum_{i=1}^{min(n,m)}(n-{\left \lfloor \frac{n}{i} \right \rfloor}i)(m-{\left \lfloor \frac{m}{i} \right \rfloor}i)\\
=\sum_{i=1}^{n}\sum_{j=1}^{m}(n-{\left \lfloor \frac{n}{i} \right \rfloor}i)(m-{\left \lfloor \frac{m}{j} \right \rfloor}j)-\sum_{i=1}^{min(n,m)}(nm+{\left \lfloor \frac{n}{i} \right \rfloor}{\left \lfloor \frac{m}{i} \right \rfloor}i^2-(m{\left \lfloor \frac{n}{i} \right \rfloor}+n{\left \lfloor \frac{m}{i} \right \rfloor})i)
$
积性函数
首先，我们定义整数集合上的数论函数：定义域和值域都在整数集合中的函数称为数论函数;
（真正的数论函数定义有所不同，可以自行参考维基）
那么积性函数就是这样的一类数论函数：
若函数$f$是积性函数，那么对于任意$gcd\left(i,j\right)=1$，有$f\left(i\ast j\right)=f\left(i\right)\ast f\left(j\right)$
如果函数$f$在$gcd\left(i,j\right)\neq1$时也满足后面的条件，称函数$f$为完全积性函数
常见的积性函数：
$\mu\left(i\right)$，莫比乌斯函数
$\varphi\left(i\right)$，欧拉函数
$d\left(i\right)$，约数个数函数
$\sigma\left(i\right)$，约数和函数
常见的完全积性函数（注意完全积性函数一定是积性函数）
$I\left(i\right)=1$，常函数
$\varepsilon\left(i\right)=\left[i=1\right]$，单位函数
$id\left(i\right)=i$，恒等函数
狄利克雷卷积
嗯这个东西，是今天我要讲的大部分东西的基础
那么狄利克雷卷积就是两个数论函数，通过一定的方法相乘：
定义$\left(g\ast f\right)\left(i\right)=F$，我们称F函数是g和f函数关于i的狄利克雷卷积
F的计算方式如下：
$F\left(i\right)=\sum_{d|i}g\left(d\right)f\left(\frac id\right)$
还是比较好理解的吧？
狄利克雷卷积满足交换律、结合律，并且有一些经典的结论：
$\left(\mu\ast I\right)=\varepsilon$
$\left(\varphi\ast I\right)=id$
$\left(\mu\ast id\right)=\varphi$
$\left(I\ast I\right)=d$
$\left(I\ast id\right)=\sigma$
其中前面三个，在莫比乌斯反演以及杜教筛中的应用很广泛，后面两个在解决大部分积性函数题目时候也有很大的作用
Part II 莫比乌斯函数/莫比乌斯反演
莫比乌斯函数
前面已经提到过这个东西……名字听起来很高大上对不对~
实际上它的定义不是特别高大上
定义莫比乌斯函数$\mu$
当$i=1$时，$\mu\left(i\right)=1$
当$i=\prod_{i=1}^{n}p_i^1$，其中$p_i$是互不相同的质数时，$\mu\left(i\right)=\left(-1\right)^n$
其余时候$\mu\left(i\right)=0$
$\mu$函数的两个最重要的性质，在上文中都已经用狄利克雷卷积的形式写过了
莫比乌斯函数同时也是接下来的莫比乌斯反演的主角
莫比乌斯反演
莫比乌斯反演是一个数论反演。当初发明它的主要目的是为了简化计算（1718世纪的时候）
原理
$\left(\mu\ast I\right)=\varepsilon$
实例：
设$f=\left(g\ast I\right)$
两边同时卷积一个$\mu$，变成
$f\ast\mu=g\ast I\ast\mu$
$f\ast\mu=g\ast\varepsilon=g$
莫比乌斯反演就完成了
如果写成$\sum$的形式就是这样的：
如果
$f\left(d\right)=\sum_{i|d}g\left(i\right)$
那么
$g\left(i\right)=\sum_{i|d}f\left(i\right)\mu\left(\frac di\right)$
另一种形式：
如果
$f\left(d\right)=\sum_{d|i}g\left(i\right)$
那么
$g\left(i\right)=\sum_{d|i}f\left(d\right)\mu\left(\frac di\right)$
好像在大部分莫比乌斯反演题目中后面再这一种形式更常见一些
可以把他们两个理解为“对一个东西的所有约数求和”以及“对一个东西的所有倍数求和”然后反演
为了加深理解，我们先来看一个例子
$f(x)=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=x]$
$F(x)=\sum_{i=1}^{n}\sum_{j=1}^{m}[x|gcd(i,j)]=\lfloor \frac{n}{x}\rfloor\lfloor \frac{m}{x}\rfloor$
因为$F(x)=\sum_{x|d}f(d)$
所以$f(x)=\sum_{x|d}F(d)\mu(\frac{d}{x})$
注意这里面就是把一个不太好求的东西求了一个和，然后变成了一个很好求的东西，再通过反演把它反向算出来
再来看下一个例子：求
$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd\left(i,j\right)$
我们做一步变形，一步非常重要的变形：把$gcd\left(i,j\right)$的值提出来，变成：
$\sum_{d=1}^{n}d\sum_{i=1}^{n}\sum_{j=1}^{m}\left[gcd\left(i,j\right)=d\right]$
这一步非常重要，一定要好好理解再继续，因为它是一个超级常用的技巧
下一步，发现后面$gcd\left(i,j\right)=d$这里的$d$很烦呐，把它除上去：
$\sum_{d=1}^{n}d\sum_{i=1}^{\frac nd}\sum_{j=1}^{\frac md}\left[gcd\left(i,j\right)=1\right]$
看到了吗？这就完成了向的转变，后面就反演一下，变成这个形式：
$\sum_{d=1}^{n}d\sum_{i=1}^{n}\mu\left(i\right)\frac n{id}\frac m{id}$
设$D=id$，我们先枚举D再枚举D的约数d，变成这个形式
$\sum_{D=1}^{N}\sum_{d|D}d\mu\left(\frac Dd\right)\frac n{id}\frac m{id}$
最后面两项提到前面去，变成
$\sum_{D=1}^{N}\frac n{D}\frac m{D}\sum_{d|D}d\mu\left(\frac Dd\right)$
发现后面的是一个卷积的形式，就是$\left(\mu\ast id\right)=\varphi$
所以得到最终结果：
$\sum_{D=1}^{N}\frac n{D}\frac m{D}\varphi\left(D\right)$
然后数论分块技巧，在$O\left(\sqrt n\right)$下解决
_【例题】_
${\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}\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}\sum_{k|i,k|j}\mu (k)ijg}$
令$S[n]=\sum_{i=1}^{n}i$，则
原式${=\sum_{d=1}^{n}d\sum_{k=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu (k)k^2 S(\left \lfloor \frac{n}{gt} \right \rfloor) S(\left \lfloor \frac{m}{gt} \right \rfloor)}$
令$T=gt$，换元得：
原式${=\sum_{T=1}^{n}S(\left \lfloor \frac{n}{T} \right \rfloor)S(\left \lfloor \frac{m}{T} \right \rfloor)T\sum_{k|T}\mu (k)k}$
不妨设${f(n)=\sum_{k|n}\mu(k)\ast k}$
则$f(n)$为积性函数，可以在$O(n)$的复杂度内，做线性筛时顺便递推得到：
${f(ip)=f(i)f(p) ,}$ $i$ $mod$ $p$ ${\neq 0}$
${f(i*p)=f(i) ,}$ $i$ $mod$ $p$ ${=0}$
（$p$为质数）
总复杂度：$O(n)$
变形:
$BSOJ4127$
求$\sum_{i=1}^{n} lcm(i,n)$
$\sum_{i=1}^{n} lcm(i,n)$
$=\sum_{i=1}^{n} i \cdot n/gcd(i,n)$
$=n\sum_{i=1}^{n} i/gcd(i,n)$
$=n\sum_{d|n}\sum_{i=1}^{n} \frac{i}{d}[gcd(i,n)==d]$
$=n\sum_{d|n}\sum_{i=1}^{n/d} \frac{i}{d}[gcd(id,n)==d]$
$=n\sum_{d|n}\sum_{i=1}^{n/d} i[gcd(i,n/d)==1]$
$=n\sum_{d|n}\sum_{i=1}^{d} i[gcd(i,d)==1]$
$=n\sum_{d|n}\frac{\varphi(d)d}{2}$
记一个结论:
$d(i \ast j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]$
$\sum\limits_i^n \sum\limits_j^m f(gcd(i,j))$
$=\sum\limits_d f(d) \sum\limits_i^n \sum\limits_j^m [gcd(i,j)==d]$
$=\sum\limits_d f(d) \sum\limits_i^{\lfloor\frac{n}{d}\rfloor} \sum\limits_j^{\lfloor\frac{m}{d}\rfloor} [gcd(i,j)==1]$
$=\sum\limits_d f(d) \sum\limits_i^{\lfloor\frac{n}{d}\rfloor} \sum\limits_j^{\lfloor\frac{m}{d}\rfloor} \sum_{d|i,d|j} \mu(d)$
$=\sum_d f(d) \sum_k \mu(k) \lfloor\frac{m}{kd}\rfloor \lfloor\frac{n}{kd}\rfloor$
令$T=kd$
$=\sum_T \lfloor\frac{m}{T}\rfloor \lfloor\frac{n}{T}\rfloor \sum_{d|T} f(d) \mu(\frac{T}{d})$