笔记 · 狄利克雷卷积和数论技巧

狄利克雷卷积：

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$ 也为积性函数。
$f*\epsilon=f$ ，其中 $\epsilon(n)=[n=1]$ ， $[\cdot]$ 为埃文斯括号。单位函数是狄利克雷卷积的单位元。

常见数论函数

单位函数 $\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

的个数，根据定义可知

n=\sum_{i=0}^n f(i)

（事实上，

i|n

时

f(i)

才有值）

对

\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=\text{id}

等号两边同时卷

\mu

：

左边=\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

\mu * f=\mu*1*g=\epsilon*g=g

，Q.E.D

形式二：

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)

N\le 5\times 10^4,1\le a_i\le 5\times 10^4

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;
}

笔记 · 狄利克雷卷积和数论技巧

文章操作

狄利克雷卷积：

性质：

常见数论函数

常用结论

1. $\varphi * 1=\text{id}$

2. $\mu *1=\epsilon$

3. $\mu*\text{id}=\varphi$

4. $1*1=d$

5. $\text{id}*1=\sigma$

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

莫比乌斯反演

推式子常见思路

好题记录

I.P3911

相关推荐

评论

笔记 · 狄利克雷卷积和数论技巧

文章操作

狄利克雷卷积：

性质：

常见数论函数

常用结论

1. φ∗1=id\varphi * 1=\text{id}φ∗1=id

2. μ∗1=ϵ\mu *1=\epsilonμ∗1=ϵ

3. μ∗id=φ\mu*\text{id}=\varphiμ∗id=φ

4. 1∗1=d1*1=d1∗1=d

5. id∗1=σ\text{id}*1=\sigmaid∗1=σ

6. d(i⋅j)=∑x∣i∑y∣j[gcd⁡(x,y)=1]d(i\cdot j)=\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]d(i⋅j)=∑x∣i​∑y∣j​[gcd(x,y)=1]

莫比乌斯反演

推式子常见思路

好题记录

I.P3911

相关推荐

评论

1. $\varphi * 1=\text{id}$

2. $\mu *1=\epsilon$

3. $\mu*\text{id}=\varphi$

4. $1*1=d$

5. $\text{id}*1=\sigma$

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