笔记 · 狄利克雷卷积 和 数论技巧
aleph_
·
·
个人记录
狄利克雷卷积：
h(n)=\sum_{d|n}f(d)g(\frac{n}{d})
记作 h=f*g
另一种形式：h(n)=\sum_{xy=n}f(x)g(y)，是一样的。
性质：
- 满足交换律（易得，因为 d 和 \frac{n}{d} 地位相同）
- 满足结合律（(f*g)*h=f*(g*h)）
- 满足对函数加法的分配律（f*(g+h)=f*g+f*h）
- 如果 f,g 均为积性函数，则 f*g 也为积性函数。
-
常见数论函数
- 单位函数 \epsilon(n)=[n=1]
- 幂函数 \text{id}_k(n)=n^k，k=1 时为恒等函数 \text{id}(n)=n
- 欧拉函数 \varphi(n)
- 莫比乌斯函数 \mu(n)
- 约数个数函数 d(n)=\sum_{d|n}1
- 因数和函数 \sigma(n)=\sum_{d|n}d
常用结论
1. \varphi * 1=\text{id}
证明：
方法1：
由于欧拉函数是积性函数，设 n=\prod_{i=1}^k p_i^{c_i}，只需证 n'=p^c 时，\sum_{d|n'}\varphi(d)=n' 即可。
由于 p 是质数，d=p^0,p^1,p^2,\dots,p^c
因此 \sum_{d|n'}\varphi(d)=\sum_{i=0}^c \varphi(p^i)=1+p^0\cdot(p-1)+p^1\cdot(p-1)+\cdots+p^{c-1}\cdot(p-1)=1+(p-1)\cdot\frac{p^c-1}{p-1}=p^c
原命题得证。
方法2:
设 f(x) 为满足 \gcd(k,n)=x(k\le n) 的 k 的个数，根据定义可知
对 $\gcd(k,n)=x$ 两边同时除以 $x$：
得到 $\gcd(\frac{k}{x},\frac{n}{x})=1(k\le n)
会发现，满足上述条件的数的个数是 \varphi(\frac{n}{x})（这实际上是欧拉函数的定义）
\therefore f(x)=\varphi(\frac{n}{x})
\because n=\sum_{d|n} f(d)
\therefore n=\sum_{d|n}\varphi(\frac{n}{d})
即 \text{id}=1*\varphi，Q.E.D
最终的到的式子相当于
n=\sum_{d|n}\varphi(d)
这个式子十分关键。用 \gcd(i,j) 替换掉 n 后，可进行如下变形：
\gcd(i,j)=\sum_{d|\gcd(i,j)}\varphi(d)
=\sum_d\sum_{i=1}^n [d|i][d|n]\varphi(d)
2. \mu *1=\epsilon
证明：
设 n=\prod_{i=1}^k p_i^{c_i}，n'=\prod_{i=1}^k p_i，要证 \sum_{d|n}\mu(d)=[n=1]
注意到 c_i\ge 2 时对答案无贡献，因此
\sum_{d|n}\mu(d)=\sum_{d|n'}\mu(d)
考虑对于 n' 的所有因子 d，答案实际上只和 d 包含的质因子个数 i 有关。枚举所有因子的过程可以看成从 k 个质因子中选 i(0\le i\le k ) 个，有 \binom{k}{i} 种选择方法，贡献为 (-1)^i,
原式 =\sum_{i=0}^k \binom{k}{i}(-1)^i
由二项式定理，这就是 (1+(-1))^k
该式子当且仅当 k=0，即 n=1 时为 1，其余时候均为 0，这正好是 \epsilon(n) 的意义，Q.E.D
有一个重要的反演结论可由此得出
[\gcd(i,j)=1]=\sum_{d|\gcd(i,j)}\mu(d)
证明： 只需将 n 替换成 \gcd(i,j) 即可。
3. \mu*\text{id}=\varphi
$左边=\varphi*(1*\mu)=\varphi*\epsilon=\varphi
右边=\text{id}*\mu=\sum_{d|n}d\cdot\mu(\frac{n}{d})
因此可以得到
\varphi(n)=\sum_{d|n}d\cdot\mu(\frac{n}{d})=\sum_{d|n}\mu(d)\frac{n}{d}
4. 1*1=d
5. \text{id}*1=\sigma
6. d(i\cdot j)=\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]
莫比乌斯反演
形式一：
f(n)=\sum_{d|n}g(n) \Leftrightarrow g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})
证明：
即已知 f=g*1，求证 g=\mu * f
形式二：
$$f(n)=\sum_{n|d}g(n)\Leftrightarrow g(n)=\sum_{n|d}\mu(d)f(\frac{d}{n})$$
**证明：**
不是常规狄利克雷卷积形式了，不能直接卷积证，但是可以代数变形，逆推该式子。
$$\sum_{n|d}\mu(d)f(\frac{d}{n})=\sum_{n|d}\mu(\frac{d}{n})f(d)$$
令 $d=kn$，枚举 $k$（这一步是为了把 $n$ 单独拎出来，再代入 $g$）
$$=\sum_{k=1}^{+\infin}\mu(k)f(kn)$$
$$=\sum_{k=1}^{+\infin}\mu(k)\sum_{kn|d}g(d)$$
交换枚举顺序（目的是为了利用 $\mu *1 =\epsilon$）
$$=\sum_{n|d}g(d)\sum_{k|\frac{d}{n}}\mu(k)$$
$$=\sum_{n|d}g(d)\epsilon(\frac{d}{n})$$
当且仅当 $d=n$ 时，$\epsilon(\frac{d}{n})=1$.
$$=g(n)$$
Q.E.D
### 推式子常见思路
- 改变枚举顺序，以进行构造
- 把无关项提出/放入
- $\gcd(a,b)$ 处理思路 $1$: 将其设为 $g$ 后，乘以 $[\gcd(a,b)=g]$，也就是 $[\gcd(\frac{a}{g},\frac{b}{g})=1]$，用 $\mu$ 的反演
- $\gcd(a,b)$ 处理思路 $2$: 将其看作 $\text{id}(\gcd(a,b))$，用 $\varphi$ 的反演
- $\gcd(a,b)=g$ 的隐藏结论是 $g|a$ 且 $g|b
-
改变变量含义，如原来枚举因数，现在枚举原数和因数之比。目的可以是为了消埃文森括号，或者为了方便枚举。
比如在「Crush的电子表格」这题中，有一步经典的转化，原式为
\sum_{i=1}^n\sum_{j=1}^m\sum_{d|i,d|j,\gcd(\frac{i}{d},\frac{j}{d})=1} \frac{i\cdot j}{d}
为了方便枚举，考虑改变枚举顺序，把 d 放到前面去，同时令 i'=\frac{i}{d},j'=\frac{j}{d}，从而连续枚举。原本的条件可以变为埃文斯括号，后续替换成 \mu 进一步化简。
\sum_{d=1}^n d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]i\cdot j
这样就把 d 分离了出来，实现了简化式子的目的。
好题记录
I.P3911
题意：求
\sum_{i=1}^N\sum_{j=1}^N \text{lcm}(a_i,a_j)
$a_i$ 的性质是不优美的。考虑**改变变量意义**（该技巧在本题内频繁出现），直接枚举数的值，设 $c_i$ 为 $i$ 这个数在序列 $a$ 中出现的次数，$n$ 为 $a$ 中的最大数，则问题转化为：
$$\sum_{i=1}^n\sum_{j=1}^n c_i\cdot c_j\cdot\text{lcm}(i,j)$$
$$=\sum_{i=1}^n\sum_{j=1}^n c_i\cdot c_j\cdot\frac{i\cdot j}{\gcd(i,j)}$$
这里有个常见技巧，令 $g=\gcd(i,j)$，枚举 $g$，并改变 $i,j$ 意义为 $i'=\frac{i}{g},j'=\frac{j}{g}$，则原式变为
$$=\sum_{g=1}^n g\sum_{i=1}^{\lfloor\frac{n}{g}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{g}\rfloor} c_{ig}\cdot c_{jg}\cdot ij\cdot[\gcd(i,j)=1]$$
再进行莫比乌斯反演
$$=\sum_{g=1}^n g\sum_{i=1}^{\lfloor\frac{n}{g}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{g}\rfloor} c_{ig}\cdot c_{jg}\cdot ij\cdot\sum_{d|\gcd(i,j)}\mu(d)$$
可以知 $d|i,d|j$。把 $d$ 往前提出，并改变 $i,j$ 意义为 $i'=\frac{i}{d},j'=\frac{j}{d}$，原式变为
$$=\sum_{g=1}^ng\cdot(\sum_{d=1}^{\lfloor\frac{n}{g}\rfloor}\mu(d)\cdot d^2)\cdot (\sum_{i=1}^{\lfloor\frac{n}{gd}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{gd}\rfloor} c_{igd}\cdot i\cdot c_{jgd}\cdot j)$$
由于 $i,j$ 地位相等，因此可以变为
$$=\sum_{g=1}^ng\cdot(\sum_{d=1}^{\lfloor\frac{n}{g}\rfloor}\mu(d)\cdot d^2)\cdot (\sum_{i=1}^{\lfloor\frac{n}{gd}\rfloor}c_{igd}\cdot i)^2$$
然鹅这样还不可以实现预处理第一个括号，需要把两个括号互相独立。
考虑第一个括号实际上就是
$$\sum_{gd=1}^n\mu(d)\cdot d^2$$
注意此处 $d$ 的含义不变。不妨枚举 $k=gd$，有
$$=\sum_{k=1}^n k\cdot(\sum_{d|k}\mu(d)\cdot d)\cdot(\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}i\cdot c_{ik})^2$$
这样两个括号的范围就都只和 $k$ 有关了，可以独立计算。
其中第一个括号可以进行 $\mathcal{O}(n\log n)$ 预处理，第二个括号可以暴力计算，总计算时间复杂度为 $\mathcal{O}(n\log n)$，可以通过本题。
Code：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=50005;
int n,a[N];
int prime[N],cnt=0,mu[N],f[N],c[N];
bool vis[N];
void init(){
mu[1]=1;
for(int i=2;i<=N-5;i++){
if(!vis[i]){
prime[++cnt]=i;
mu[i]=-1;
}
for(int j=1;j<=cnt&&i*prime[j]<=N-5;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0){
mu[i*prime[j]]=0;
break;
}
else mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=N-5;i++){
for(int j=i;j<=N-5;j+=i){
f[j]+=mu[i]*i;
}
}
}
signed main(){
init();
cin>>n;
int m=0;
for(int i=1;i<=n;i++){
cin>>a[i];
c[a[i]]++;
m=max(m,a[i]);
}
n=m;
int ans=0ll;
for(int k=1;k<=n;k++){
int tmp=0ll;
for(int i=1;i<=n/k;i++){
tmp+=i*c[i*k];
}
ans+=k*f[k]*tmp*tmp;
}
cout<<ans<<endl;
}
```