mobius

（别问我为什么这么眼熟，我是贺的cmd的博客

狄利克雷卷积与数论函数

定义：数论函数，就是值域为整数的函数

两个数论函数的狄利克雷卷积是一个新函数。

比如$f(n),g(n)$的狄利克雷卷积写成$f*g$

定义$(f*g)(n) = \sum_{d|n}f(d)g(n/d)$（就是f数组的d乘上g数组的n/d

$(f*g)(10) = f(1)g(10)+f(2)g(5)+f(5)g(2)+f(10)g(1)$

狄利克雷卷积满足交换律和结合律

$f*g = g*f$

$(f*g)*h = f*(g*h)$

几个简单的数论函数

$I(n)$恒等于1，称作恒等函数

$\epsilon(n)$或者说$e(n)$当n等于1的时候为1，否则是0，被称作元函数，因为它是卷积的单位元$(\epsilon*f) = f$ (重要)

$id(n) = n$被称作单位函数

上述三个都是完全积性函数

定义：完全积性函数：对于任意的整数a,b有的$I(ab) = I(a)*I(b)$

附上两个后面会讲的例子：

$\varphi(n)$欧拉函数

$\mu(n)$被称作莫比乌斯函数

这两个函数是积性函数

定义：积性函数：对于一个函数F，如果说$gcd(a,b) = 1$时$F(ab) = F(a)*F(b)$就是积性函数

下面是一些性质：

• 积性函数F,F(1) = 1

• 积性函数F$F(x) = F(p1^{k1})F(p2^{k2})...F(pm^{km})$

  上面的p和k是算术基本定理

• 两个积性函数的卷积还是一个积性函数

• 积性函数的逆也还是积性函数

  逆：满足$e = g*f$的时候他俩互逆

  是可以进行构造的

  cmd

莫比乌斯反演的公式

有两个函数F，f

设两个函数有如下关系：$F(n) = \sum_{d|n}f(d)$

那么：$F(n) = \sum_{d|n} (1*f(d))$

也就相当于：$F = I*f$

现在如果说有f函数就可以求出来F函数了

但是如果有了F函数，求f咋办？求逆？

啊对$F = I*f,f = F*I^{-1}$

mobius把$I^{-1}$命名为$\mu$

问题是这个函数咋求？

他是个积性函数（因为上面有说过，积性函数的逆还是积性函数

在研究一个积性函数的时候，先研究它在质数的幂的时候的表现

比如说$\mu(p^k)(p是质数)$

k = 0的时候，$\mu(1) = 1$

k = 1的时候，由于$\sum_{d|p}I(d)\mu(p/d) = e(p) = 0$所以$\mu(p) = -1$

k>1的时候，还是等于0

然后定义慢慢慢慢的出来：

$\mu(x) = 0$（当x可以被一个大于1的某个正数的平方整除的话

$\mu(x) =(-1)^k$k为x含有的质因子的种类数

然后我们来康康莫比乌斯的反演公式：

• 嵌入式莫比乌斯反演

  我们从$\mu*I = e$得：$\sum_{d|n}\mu(d) = [n=1]$（这个中括号是用来判断真假的）

  注意到$[n|m][n/m =1] = [n=m]$

  则有：$[n|m]\sum_{d|(n/m)}\mu(d) = [n = m]$

• 约数的莫反

  若：$F(n) = \sum_{d|n} f(d)$

  则：$f(n) = \sum_{d|n} \mu(d) F(n/d)$

  又作$f(n) = \sum_{d|n}\mu(n/d)F(d)$（等价

  根据$\mu = I^{-1} 有 f*I = F->f = F*\mu$

• 倍数的莫比乌斯反演

  若：$F(n) = \sum_{n|d} f(d)$

  则：$f(n) = \sum_{n|d}\mu(d/n)F(d)$

  并不是狄利克雷卷积的形式，狄利克雷一般后边F应该是F（n）

  又作$F(n) = \sum_{k}^{\infty}f(kn)与f(n) = \sum_{k}^{\infty} \mu(k)F(kn)$

整除分块：

cmd

莫反基本上所有的题都要整除分块……因为复杂度问题

其他的数论函数

• 恒等函数： $I(n)$，永远等于1，完全积性
• 元函数：$\epsilon(n)$当n=1的时候为1否则是0 完全积性
• 单位函数：$id(n)$函数值为n，完全积性
• 幂函数：$id^x(n)$函数值为$n^x$完全积性
• 莫比乌斯函数：$\mu(n)$$\mu *I = \epsilon$积性
• 欧拉函数：$\varphi(n)$小于等于n的所有数字中和n互质的 积性
• 约数个数函数：$d(n)$n的约数个数 积性
• 约数和函数：$σ(n)$n的约数和 积性
• 除数函数：$σ^k(n)$n的约数k次方和 积性

$\varphi$的性质：

• 积性函数
• $\varphi(p^k) = (p-1)p^{k-1}$(p质数)
• $p|n,\varphi(np) = \varphi(n)*p$(p质数)
• $\varphi(n = p_1^{k_1}p_2^{k_2}...p_m^{k_m} = n*(\dfrac{p_1-1}{p_1}*\dfrac{p_2-1}{p_2}*...*\dfrac{p_m-1}{p_m}))$

一些狄利克雷卷积结论：

• $id = I*\varphi$
• 等价于：$id*\mu = \varphi$

这个结论在求$\sum_{i=1}^{n}\sum_{j=1}^{m}$的时候：

$$\sum_{d = 1}^{n}d*\sum_{t=1}^{n/d}\mu(t)(n/dt)(m/dt)(莫反)\\ 设p = dt,\\原式= \sum_{d =1}^{n}d*\sum_{d|p}^{n}\mu(p/d)(n/p)(m/p)\\ = \sum_{p=1}^{n}\sum_{d|p}d*\mu(p/d)(n/p)(m/p)\\ = \sum_{p=1}^{n}\varphi(p)(n/p)(m/p)$$

除数函数相关：

• $d = I*I$
• $σ = id*I$
• $d(n) = (k_1+1)(k_2+1)...(k_m+1)$
• $σ(n) = (1+p_1+p_1^2+...+p_1^{k_1})(1+p_1+p_2^2+...+p_2^{k_2})...(1+p_m+p_m^2+...+p_m^{k_m})$
• $\sum_{i=1}^{n}d(n) = \sum_{i=1}^{n}(n/i)$
• $d(ij) = \sum_{x|i}\sum_{y|j}[x⊥y]$
• $\varphi(ij) = \dfrac{\varphi(i)\varphi(j)(i,j)}{\varphi((i,j))}$

题目

P3455

这个题比较偏板子一点

我们把题目写出来：求$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==d]$

当然我们可以直接转换拉：$\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[gcd(i,j)==1]$

下面的n,m都除以d

用嵌入式反演转换：

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

然后我们交换求和的顺序：

$\sum_{d=1}^{min(n,m)}\mu(d) \sum_{d|i}^{n}\sum_{d|j}^{m}1$

然后我们想到，小于等于n或者m的可以整除d的数字个数是有限的：

$\sum_{d=1}^{min(n,m)}(n/d)(m/d)\mu(d)$

然后整除分块

P2257

首先一样是把题目整理一遍：

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

当然了，我们像是上面一道题一样转化一下：

$ans =\sum_{p\in prime}\sum_{i=1}^{n/p}\sum_{j=1}^{m/p}\sum_{d|gcd(i,j)}\mu(d)\\=\sum_{p\in prime}\sum_{d=1}^{min(n/p,m/p)}\mu(d)*(n/dp)*(m/dp)$

然后我们就考虑一下，枚举T = dp

$\sum_{T=1}^{min(n,m)}(n/T)(m/T)\sum_{p\in prime,p|T}\mu(\dfrac{T}{p})$

前面的部分显然是可以整除分块的，后面的预处理出来，枚举p然后枚举p的倍数

P5221

把式子改变:$\prod_{i=1}^{n}\prod_{j=1}^{n}\dfrac{i*j}{gcd(i,j)^2}$并且模数是个质数

我们就分开求呗，上面那个好说：$(n!)^{2n}$

下边那个难：我们考虑求出来gcd是d的数对个数之后就可以求出来积（快速幂

所以我们设$G(x,y)表示\sum_{i=1}^{y}\sum_{j=1}^{y}[gcd(i,j)==x]$

那么原式就可以变成：$\prod_{i=1}^{n}i^{G(i,n)}$

但是我们并不能把所有的$G(1...n,n)$求出来因为复杂度非常不对劲

但是把改一下$G(i,n) = G(1,n/i)$呢……

所以我们能求出来$G(1,n)$就好了

然后我们考虑设$f(x) = \sum_{i=1}^{n}\sum_{j=1}^{n}[x|gcd(i,j)]，F(x) = \sum_{i=1}^{n}\sum_{j=1}^{n}[x==gcd(i,j)]$

但是显然……$f[x] = \sum_{x|d}F[d]$

然后反演啊：$F[d] = \sum_{d|n}\mu(n/d)f(n)$

显然F函数就是G

那么我们就进行求解：$f(x) = (n/x)^2$

$F[1] = \sum_{d=1}^{n}\mu(d)f(d) = \sum_{d=1}^{n}\mu(d)(n/d)^2$

然后对n/d进行整除分块

然后在求F数组的时候，对于每一个x求一遍是不优的

我们发现n/x只有根号n种取值，还可以再开一次整除分块……

P3172

我们这么考虑：对于我们先求出来公约数为k的，然后减去它的倍数就好对吧（容斥

由于$h-l\le 1e5$所以我们可以直接枚举gcd因为gcd一定小于等于两数之差（更相减损

枚举了之后减去倍数的答案就好，注意倒序枚举

P2522

这个题……

我们考虑，$a-b,c-d$是不是可以用$1-b,1-d$减去$1-(b-1),1-d$减去$1-b,1-(d-1)$加上$1-(c-1),1-(d-1)$

就完了

P3372

这个题……非常好

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

$\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij) = \sum_{i=1}\sum_{j=1}\sum_{x|i}\sum_{y|j}[gcd(x,y) = 1]$

改变求和顺序：

$\sum_{x=1}^{n}\sum_{y=1}^{m}(n/x)(m/y)[gcd(x,y)=1]$

然后莫反一下

设$g(x) = \sum_{x|d}f(d)$

$g(x) = \sum_{i=1}^{n}\sum_{j=1}^{m}(n/i)(m/i)[x|gcd(i,j)]\\=\sum_{i=1}^{n/x}\sum_{j=1}^{m/x}(n/ix)(m/jx)$

$f(1) = \sum_{i=1}^{n}\mu(i)g(i)$

g函数整除分块就好了=-

1829

套路：

推式子开始：(假设n<m)

$$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j) = \sum_{i=1}^{n}\sum_{j=1}^{m}\dfrac{i*j}{gcd(i,j)}\\ = \sum_{d=1}^{n}d*\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==d]*i*j/d^2 \\ = \sum_{d=1}^{n}d*\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[gcd(i,j)==1]*i*j \\$$

然后我们把d后边的那点东西拿出来，假设n = n/d,m = m/d

$$\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)==1]*i*j \\ = \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}\mu(d)*i*j \\ = \sum_{d=1}^{n}\mu(d)\sum_{i=1,d|i}^{n}\sum_{j=1,d|j}^{m}i*j \\ = \sum_{d=1}^{n}\mu(d)*d^2\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}i*j$$

前面的关于d的东西我们可以前缀和（线性筛的时候前缀和

后边的可以直接一个式子算出来

这个后边的东西就可以O(1)求出来了

整个的东西用一次整除分块

那么把这个东西设成$sum(n,m)$的话，原式变成：$\sum_{d=1}^{n}d*sum(n/d,m/d)$

我们惊喜的发现，这玩意又是一个整除分块啊

然后O(n)的复杂度就可以做了

P3704

这个题我们对于每一个f都记录一下用过多少次

先提示一下复杂度：$(nlogn+\sqrt n *q)$

再提示一下瓶颈：调和级数

好了开始推式子

我们可以把式子写成这个样子：(默认n<m)

$$\prod_{d=1}^{n}f[d]\prod_{i=1}^{n}\prod_{j=1}^{m}[gcd(i,j)==d] \\ = \prod_{d=1}^{n}f[d]^{\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[gcd(i,j)==1]}$$

里层外层函数可以各用一次整除分块，这样可以得到O(n)的做法（其实考场上想到这里就可以先放一放了，因为有70分了

把上面的东西拿出来：

$$\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[gcd(i,j)==1] \\ = \sum_{i=1}^{n/d}\sum_{j=1}^{m/d}\sum_{t|gcd(i,j)}\mu(t) \\ = \sum_{t=1}^{n/d}\mu(t)(n/dt)(m/dt)$$

这个东西很好用啊，因为后边有个dt，我们把dt设成T

$$\prod_{T=1}^{n}(\prod_{d|T}f[d]^{\mu(T/d)})^{(n/T)(m/T)}$$

然后我们对n/T,m/T进行整除分块，d的东西咋办啊，我们发现T最大是1e6的，那么我们调和级数算出来每一个T对应的里面的东西就好啦……