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})\)

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

例一\(BSOJ2019\)

【题意】:求\(\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} \rfloor*i}\)
\(=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\)

for(l=1;l<=n;l=r+1){
    r=(k/l)?min(k/(k/l),n):n;
    ans+=(k/l)*Sum(l,r);
}

例二\(BSOJ3713\)

$\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)\)下解决

【例题】

\(BSOJ3431\)&
\(BSOJ4129\)

\({\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(i*p)=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}\)

\(BSOJ4347\)

记一个结论:

\(d(i \ast j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)==1]\)

题解

\(BSOJ4372\)

\(\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})\)