狄利克雷卷积

定义

数论函数

定义域为正整数的函数，称为数论函数。

常见数论函数：

函数符号	名称	定义
$\epsilon (n)$	单位函数	$\epsilon (n)=[n=1]$，即仅当 $n=1$ 时为 $1$，其余为 $0$
$1(n)$	常数函数	$1(n)=1$，对任意正整数取值都为 $1$
$\mathrm{id}(n)$	恒等函数	$\mathrm{id}(n)=n$
${\mathrm{id}}_k(n)$	幂函数	${\mathrm{id}}_k(n)=n^k$
$\mu (n)$	莫比乌斯函数	按照因子个数取 $(-1{)}^k$ 或 $0$
$\phi (n)$	欧拉函数	$1\sim n$ 中与 $n$ 互质的数的个数
$d(n)$	约数个数函数	$n$ 的正约数的个数
$\sigma (n)$	约数和函数	$n$ 的所有正约数的和

狄利克雷卷积

狄利克雷卷积就是在数论函数上的一种乘法运算，将复杂的交换求和过程转化成类似整式乘法的卷积运算，缩短公式的推导。

同时将欧拉函数，约数和函数通过简单的卷积运算得到。

狄利克雷卷积的定义公式

设 $f,g$ 是两个数论函数，它们的狄利克雷卷积记作 $f\ast g$，结果仍是一个数论函数，其定义为：

$$(f\ast g)(n)=\sum _{d\mid n}f(d)\cdot g\left(\frac{n}{d}\right)$$

性质

交换律：

$$f\ast g=g\ast f$$

结合律：

$$(f\ast g)\ast h=f\ast (g\ast h)$$

分配律：

$$f\ast (g+h)=f\ast g+f\ast h$$

单位函数：

单位函数 $\epsilon$ 是狄利克雷卷积的单位元，即对任意数论函数 $f$，有

$$f\ast \epsilon =f$$

卷积逆元：

对于满足 $f(1)\ne 0$ 的数论函数 $f$，存在唯一的函数 $f^{-1}$，使得
$$f\ast f^{-1}=\epsilon$$
称 $f^{-1}$ 为 $f$ 的狄利克雷逆元。

特殊等式

1. $$1\ast \mu =\epsilon$$
2. $$1\ast 1=d$$
3. $$1\ast id=\sigma$$
4. $$1\ast \phi =id$$
5. $$id\ast \mu =\phi$$

证明可以带入前面的狄利克雷卷积的定义式中。

所以前面的莫比乌斯反演的第一形式可以用这特殊等式轻松证明，证明如下：

定理：若 $F=f\ast 1$，即
$$F(n)=\sum _{d\mid n}f(d)$$
则有
$$f(n)=\sum _{d\mid n}F(d)\cdot \mu \left(\frac{n}{d}\right)$$

已知 $F=f\ast 1$，两边同时右乘 $\mu$：
$$F\ast \mu =(f\ast 1)\ast \mu$$

由结合律：
$$F\ast \mu =f\ast (1\ast \mu )$$

代入 $1\ast \mu =\epsilon$：
$$F\ast \mu =f\ast \epsilon =f$$

证毕。

积性定理

若 $f$ 和 $g$ 都是积性函数，则它们的狄利克雷卷积 $f\ast g$ 也是积性函数。

证明：设 $\gcd (a,b)=1$，需证
$$(f\ast g)(ab)=(f\ast g)(a)\cdot (f\ast g)(b)$$

展开左边：
$$(f\ast g)(ab)=\sum _{d\mid ab}f(d)g(ab/d)$$

由于 $a,b$ 互质，$ab$ 的每个约数 $d$ 都可以唯一拆分为 $d=d_1{d}_2$，其中 $d_1\mid a$，$d_2\mid b$，且 $\gcd (d_1,d_2)=1$。

代入得：
$$(f\ast g)(ab)=\sum _{d_1\mid a}\sum _{d_2\mid b}f(d_1{d}_2)g\left(\frac{a}{d_1}\cdot \frac{b}{d_2}\right)$$
$$=\sum _{d_1\mid a}\sum _{d_2\mid b}f(d_1)f(d_2)g(a/d_1)g(b/d_2)$$
$$=\left(\sum _{d_1\mid a}f(d_1)g(a/d_1)\right)\cdot \left(\sum _{d_2\mid b}f(d_2)g(b/d_2)\right)$$
$$=(f\ast g)(a)\cdot (f\ast g)(b)$$

因为 $1$，$\mu$，$\mathrm{id}$ 都是积性函数，所以由它们卷积得到的 $d(n)$，$\sigma (n)$，$\phi (n)$ 也都是积性函数，所以也可以用线性筛处理。

例题

CF1900D Small GCD

传送门

我们发现我们可以先将原数组排序。

那么答案就为：

$$Ans=\sum _{i=1}^n\sum _{j=i+1}^n(n-j)gcd(a_i,a_j)$$

利用欧拉反演公式替换 $\gcd$：

$$\gcd (a_i,a_j)=\sum _{d\mid \gcd (a_i,a_j)}\phi (d)=\sum _{d\mid a_i,d\mid a_j}\phi (d)$$

代入求和式，并交换求和顺序：

$$\text{Ans}=\sum _{j=2}^{n-1}(n-j)\sum _{d\mid a_j}\phi (d)\sum _{i=1}^{j-1}[d\mid a_i]$$

观察式子最后的 ${\sum }_{i=1}^{j-1}[d\mid a_i]$，我们发现它的几何意义为在当前遍历到的 $a_j$ 之前，有多少个数是 $d$ 的倍数。

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int MAXX = 1e5 + 5, INF = 1e5 + 2;

int n, a[MAXX], num[MAXX], prime[MAXX], cnt, phi[MAXX], vis[MAXX], sum[MAXX], ans, t;

void init() {
	num[0] = 1;
	for(int i = 1; i <= INF; i++) num[i] = num[i - 1] * i;
    phi[1] = 1;
    for(int i = 2; i <= INF; i++) {
        if(!vis[i]) {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1; j <= cnt && i * prime[j] <= INF; j++) {
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else {
                phi[i * prime[j]] = phi[i] * phi[prime[j]];
            }
        }
    }
    for(int i = 1; i <= INF; i++) sum[i] = sum[i - 1] + phi[i];
}

void solve(){
    cin >> n; ans = 0;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= INF; i++) sum[i] = 0;
    sort(a + 1, a + 1 + n);
    for(int j = 1; j <= n - 1; j++){
        int num = 0;
        for(int d = 1; d * d <= a[j]; d++){
            if(a[j] % d == 0){
                num += phi[d] * sum[d];
                if(d * d != a[j]) num += phi[a[j] / d] * sum[a[j] / d];
            }
        }
        ans = (ans + num * (n - j));
        for(int d = 1; d * d <= a[j]; d++){
            if(a[j] % d == 0){
                sum[d]++;
                if(d * d != a[j]) sum[a[j] / d]++;
            }
        }
    }
    cout << ans << '\n';
}

signed main(){
    init();
    cin >> t;
    while(t--) solve();
    return 0;
}

P1829 [集训队互测 2010] Crash的数字表格 / JZPTAB

传送门

由题得：
$$Ans=\sum _{i=1}^n\sum _{j=1}^m\mathrm{lcm}(i,j)$$

将 $\mathrm{lcm}(i,j)=\frac{i\cdot j}{\gcd (i,j)}$，交换枚举顺序：

$$Ans=\sum _{d=1}^n\sum _{i=1}^n\sum _{j=1}^m[\gcd (i,j)=d]\frac{i\cdot j}{d}$$

令 $i=xd,j=yd$ 代入原式：

$$Ans=\sum _{d=1}^n\sum _{x=1}^{\lfloor n/d\rfloor }\sum _{y=1}^{\lfloor m/d\rfloor }[\gcd (x,y)=1]\cdot x\cdot y$$

所以设：

$$S(N,M)=\sum _{x=1}^N\sum _{y=1}^M[\gcd (x,y)=1]\cdot x\cdot y$$

代入 $[\gcd (x,y)=1]={\sum }_{k\mid x,k\mid y}\mu (k)$，设 $x=uk,y=vk$：

$$S(N,M)=\sum _{x=1}^N\sum _{y=1}^{M}xy\sum _{k\mid x,k\mid y}\mu (k)$$

$$=\sum _{k=1}^{\min (N,M)}\mu (k)\sum _{u=1}^{\lfloor N/k\rfloor }\sum _{v=1}^{\lfloor M/k\rfloor }(uk)\cdot (vk)$$

$$=\sum _{k=1}^{\min (N,M)}\mu (k)\cdot k^2\left(\sum _{u=1}^{\lfloor N/k\rfloor }u\right)\left(\sum _{v=1}^{\lfloor M/k\rfloor }v\right)$$

$$\left(\sum _{u=1}^{\lfloor N/k\rfloor }u\right)\left(\sum _{v=1}^{\lfloor M/k\rfloor }v\right)$$ 后面的这个可以用整除分块解决。

所以：

$$Ans=\sum _{d=1}^{\min (n,m)}d\sum _{k=1}^{\min (\lfloor n/d\rfloor ,\lfloor m/d\rfloor )}\mu (k)\cdot k^2\left(\sum _{u=1}^{\lfloor N/k\rfloor }u\right)\left(\sum _{v=1}^{\lfloor M/k\rfloor }v\right)$$

令 $T=dk$ 代入：

$$Ans=\sum _{T=1}^{\min (n,m)}\left(\sum _{u=1}^{\lfloor N/k\rfloor }u\right)\left(\sum _{v=1}^{\lfloor M/k\rfloor }v\right)\sum _{k\mid T}\frac{T}{k}\cdot \mu (k)\cdot k^2$$

虽然现在这个可以直接做了，但是我们考虑继续优化，我们观察后面的部分。

$$\sum _{k\mid T}\frac{T}{k}\cdot \mu (k)\cdot k^2=T\sum _{k\mid T}k\cdot \mu (k)$$

又因为$\sum _{k\mid T}k\mu (k)$ 是积性函数 $(\mathrm{id}\cdot \mu )$ 与 $1$ 的卷积，因此$$T\sum _{k\mid T}k\cdot \mu (k)$$ 依然是积性函数，用线性筛处理即可。

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int MAXX = 1e7 + 5, M = 20101009, INF = 1e7 + 2;

int n, m, p[MAXX], prime[MAXX], cnt, sum[MAXX], ans, vis[MAXX];

void init(){
    p[1] = 1;
    for(int i = 2; i <= INF; i++) {
        if(!vis[i]) {
            prime[++cnt] = i;
            p[i] = ((1 - i) * i % M + M) % M;
        }
        for(int j = 1; j <= cnt && i * prime[j] <= INF; j++) {
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                p[i * prime[j]] = p[i] * prime[j] % M;
                break;
            }else p[i * prime[j]] = p[i] * p[prime[j]] % M;
        }
    }
    for(int i = 1; i <= INF; i++) sum[i] = (sum[i - 1] + p[i]) % M;
}

signed main(){
    init();
    cin >> n >> m;
    for(int l = 1, r; l <= min(n, m); l = r + 1){
        r = min(n / (n / l), m / (m / l));
        ans = (ans + ((n / l) * (n / l + 1) / 2) % M * ((m / l) * (m / l + 1) / 2 % M) % M * ((sum[r] - sum[l - 1] + M) % M) % M) % M;
    }
    cout << ans << '\n';
    return 0;
}

综合题目练习

abc020D

这道题是一个典型的套路题。

我们先将 $lcm$ 转换：

$$Ans=\sum _{i=1}^n\frac{ik}{gcd(i,k)}$$

$$=\sum _{i=1}^n\sum _{d=1}^i\frac{ik}{d}[gcd(i,k/d)=1]$$

$$=\sum _{i=1}^n\sum _{d=1}^i\frac{ik}{d}\sum _{g|gcd(i,k/d)}\mu (g)$$

$$=k\sum _{d|k}\sum _{i=1}^{\lfloor n/d\rfloor }i\sum _{g|gcd(i,k/d)}\mu (g)$$

$$=k\sum _{d|k}\sum _{g|k/d}\mu (g)\sum _{i=1}^{\lfloor n/dg\rfloor }ig$$

然后预处理 $k$ 的因数即可AC此题

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int MAXX = 1e5 + 5, M = 1e9 + 7;

int n, k, num[MAXX], cnt, ans, sum[MAXX];

int mu(int n){
	int res = 1;
	for(int i = 2; i * i <= n; i++){
		if(n % i == 0){
			int zrr = 0;
			while(n % i == 0) n /= i, zrr++;
			if(zrr >= 2) return 0;
			res = -res;
		}
	}
	if(n != 1) res = -res;
	return res;
}

__int128_t SUM(__int128_t x){
	return (1 + x) * x / 2 % M;
}

signed main(){
	cin >> n >> k;
	for(int i = 1; i * i <= k; i++){
		if(k % i == 0){
			num[++cnt] = i;
			if(i * i != k) num[++cnt] = (k / i);
		}
	}
	sort(num + 1, num + 1 + cnt);
	for(int i = 1; i <= cnt; i++) sum[i] = mu(num[i]);
	for(int d = 1; d <= cnt; d++){
		int res = 0;
		for(int g = 1; g <= cnt; g++){
			if((k / num[d]) % num[g] != 0) continue;
			res = (res + sum[g] * num[g] % M * SUM(n / num[d] / num[g]) % M + M) % M;
		}
		ans = (ans + res) % M;
	}
	cout << ans * k % M;
	return 0;
}

P2231

由于裴蜀定理可以知道当为合法情况的时候仅当 g c d { a 1 , a 2 , a 3 … a n } = 1 gcd\{a_1,a_2,a_3 \dots a_n\} = 1 gcd{a1​,a2​,a3​…an​}=1

然后我们直接大力莫反：

$$\text{Ans}=\sum _{1\le a_1\le M}\cdots \sum _{1\le a_N\le M}[\gcd (a_1,\dots ,a_N,M)=1]$$

$$=\sum _{d\mid M}\mu (d)\left(\sum _{1\le a_1\le M,d\mid a_1}1\right)\cdots \left(\sum _{1\le a_N\le M,d\mid a_N}1\right)$$

$$=\sum _{d\mid M}\mu (d){\left(\frac{M}{d}\right)}^N$$

#include<bits/stdc++.h>
#define int long long

using namespace std;

int n, m, cnt, ans;

int qpow(int a, int b){
	int res = 1;
	while(b){
		if(b & 1) res = res * a;
		a = a * a, b /= 2;
	}
	return res;
}

int mu(int n){
	int res = 1;
	for(int i = 2; i * i <= n; i++){
		if(n % i == 0){
			int zrr = 0;
			while(n % i == 0) n /= i, zrr++;
			if(zrr >= 2) return 0;
			res = -res;
		}
	}
	if(n != 1) res = -res;
	return res;
}

signed main(){
	cin >> n >> m;
	for(int i = 1; i * i <= m; i++){
		if(m % i == 0){
			ans += mu(i) * qpow(m / i, n);
			if(i * i != m) ans += mu(m / i) * qpow(i, n);
		} 
	}
	cout << ans << '\n';
	return 0;
}

CF235E

前置知识：

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

有公式可转换：

$$d(i\cdot j\cdot k)=\sum _{u|i}\sum _{v|j}\sum _{w|k}[\gcd (u,v)=1][\gcd (v,w)=1][\gcd (w,u)=1]$$

然后我们暴力莫反：

$$[\gcd (u,v)=1]=\sum _{x|u,x|v}\mu (x)$$

$$[\gcd (v,w)=1]=\sum _{y|v,y|w}\mu (y)$$

$$[\gcd (w,u)=1]=\sum _{z|w,z|u}\mu (z)$$

将其带入，交换求和顺序：

$$\text{Ans}=\sum _{x=1}^a\mu (x)\sum _{y=1}^b\mu (y)\sum _{z=1}^c\mu (z)\left(\sum _{x|u,z|u}\lfloor \frac{a}{u}\rfloor \right)\left(\sum _{x|v,y|v}\lfloor \frac{b}{v}\rfloor \right)\left(\sum _{y|w,z|w}\lfloor \frac{c}{w}\rfloor \right)$$

我们设：

$$S(N,M)=\sum _{M|k}\lfloor \frac{N}{k}\rfloor =\sum _{t=1}^{\lfloor N/M\rfloor }\lfloor \frac{N}{M\cdot t}\rfloor$$

又：

$$\sum _{\text{lcm}(x,z)\mid u}\lfloor \frac{a}{u}\rfloor =S(a,\text{lcm}(x,z))$$

$$\sum _{\text{lcm}(x,y)\mid v}\lfloor \frac{b}{v}\rfloor =S(b,\text{lcm}(x,y))$$

$$\sum _{\text{lcm}(y,z)\mid w}\lfloor \frac{c}{w}\rfloor =S(c,\text{lcm}(y,z))$$

然后我们暴力处理，对于 $\mu =0$
的时候直接结束循环，并且与处理 $S$ 和 $lcm$ 即可AC此题。

将其整理：

$$\text{Ans}=\sum _{x=1}^a\mu (x)\sum _{y=1}^b\mu (y)\sum _{z=1}^c\mu (z)\cdot S(a,\text{lcm}(x,z))\cdot S(b,\text{lcm}(x,y))\cdot S(c,\text{lcm}(y,z))$$

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int MAXX = 2e3 + 5, INF = 2e3 + 2, M = 1073741824;

int a, b, c, mu[MAXX], vis[MAXX], s[MAXX][MAXX], LCM[MAXX][MAXX], ans;
vector<int> p;

void init(){
	for(int n = 1; n <= INF; n++){
		for(int m = 1; m <= n; m++){
			for(int k = 1; k <= n / m; k++) s[n][m] = (s[n][m] + n / (m * k)) % M;
		}
	}
	for(int i = 1; i <= INF; i++){
		for(int j = 1; j <= INF; j++) LCM[i][j] = i * j / __gcd(i, j);
	}
	mu[1] = 1;
    for(int i = 2; i <= INF; i++){
        if(!vis[i]) p.push_back(i), mu[i] = -1;
    	for(int j : p){
      	  if(i * j > INF) break;
      	  vis[i * j] = 1, mu[i * j] = -mu[i];
      	  if(i % j == 0){ mu[i * j] = 0; break; }
    	}
    }
}


signed main(){
	init();
	cin >> a >> b >> c;
    for(int x = 1; x <= a; x++){
        if(mu[x] == 0) continue;
        for(int y = 1; y <= b; y++){
            if(mu[y] == 0) continue;
            if(LCM[x][y] > a) continue;
            for(int z = 1; z <= c; z++){
                if(mu[z] == 0) continue;
                if(LCM[y][z] > b) continue;
                if(LCM[x][z] > c) continue;
                if(mu[x] * mu[y] * mu[z] == 1) ans = (ans + s[a][LCM[x][y]] * s[b][LCM[z][y]] % M * s[c][LCM[x][z]] % M) % M;
                else ans = (ans - s[a][LCM[x][y]] * s[b][LCM[z][y]] % M * s[c][LCM[x][z]] % M + M) % M;
            }
        }
    }
    cout << ans << "\n";
	return 0;
}

P10584

前置知识，重要恒等式

$${\mu }^2(d)=\sum _{k^2\mid d}\mu (k)$$

任意正整数 $$x$$ 表示为 $$x=d\cdot y^2$$，我们称 (d) 为“平方因子自由数”。

则 $$i\cdot j=(d_1{x}^2)\cdot (d_2{y}^2)=d_1{d}_2(xy{)}^2$$ 是完全平方数，当且仅当 $$d_1=d_2$$。

所以设 $$i=d\cdot x^2$$，$$j=d\cdot y^2$$（其中 $${\mu }^2(d)=1$$）：

• $$1\le d\cdot x^2\le n⟹1\le x\le \lfloor \sqrt{\frac{n}{d}}\rfloor$$
• $$1\le d\cdot y^2\le m⟹1\le y\le \lfloor \sqrt{\frac{m}{d}}\rfloor$$

原式可转化为对 $$d$$ 的求和：

$$\text{Ans}=\sum _{d=1}^{\min (n,m)}{\mu }^2(d)\lfloor \sqrt{\frac{n}{d}}\rfloor \lfloor \sqrt{\frac{m}{d}}\rfloor$$

我们直接将公式代入：
$$\text{Ans}=\sum _{d=1}^{\min (n,m)}\left(\sum _{k^2|d}\mu (k)\right)\lfloor \sqrt{\frac{n}{d}}\rfloor \lfloor \sqrt{\frac{m}{d}}\rfloor$$

$$=\sum _{k=1}^{\lfloor \sqrt{\min (n,m)}\rfloor }\mu (k)\sum _{t=1}^{\lfloor \min (n,m)/k^2\rfloor }\lfloor \sqrt{\frac{n}{k^{2}t}}\rfloor \lfloor \sqrt{\frac{m}{k^{2}t}}\rfloor$$

我们设：

$$h(A,B)=\sum _{t=1}^{\min (A,B)}\lfloor \sqrt{\frac{A}{t}}\rfloor \lfloor \sqrt{\frac{B}{t}}\rfloor$$

所以最终结果就为：

$$\text{Ans}=\sum _{k=1}^{\lfloor \sqrt{\min (n,m)}\rfloor }\mu (k)\cdot h\left(\lfloor \frac{n}{k^2}\rfloor ,\lfloor \frac{m}{k^2}\rfloor \right)$$

然后我们直接用二次分块加上线性筛预处理即可。

代码读者自写不难。

做题技巧

对于 $gcd(i,j)=1$ 或者 $gcd(i,j)$ 在分母的情况我们要有先用莫比乌斯反演。

对于 $gcd(i,j)$ 的普通情况我们先考虑欧拉反演公式。