狄利克雷卷积

符号即约定

  • [expression][expression] , 表示当 expressionexpression 为真时取值为 11 , 为假时取值为 00
  • 1(n)=11(n) = 1 , 常函数 ,恒为 11
  • ε(n)=[n=1]\varepsilon(n) = [n = 1] , 狄利克雷卷积单位元
  • Id(n)=nId(n) = n ,恒等函数
  • Idk(n)=nkId_k(n) = n^k , 幂函数
  • d(n)d(n) , 约数个数函数
  • σ(n)\sigma(n) , 约数和函数
  • σk(n)σ_k(n) , 除数函数,表示 nn 所有因数 kk 次方的和。
  • φ(n)\varphi(n) , 欧拉函数
  • μ(n)\mu(n) , 莫比乌斯函数
  • 无特殊说明, pip_i 为质数

定义

狄利克雷卷积 f(x)f(x)g(x)g(x) 是定义在数论函数间的一种二元运算,可以定义为:

(fg)(n)=xy=nf(x)g(y)(f*g)(n) = \sum_{xy=n}f(x)g(y)

dnf(d)g(nd)\Rightarrow\sum_{d \mid n}f(d)g(\frac{n}{d})

性质

交换律

fg=gff*g = g*f

证明

(fg)(n)=dnf(d)g(nd)(f*g)(n) = \sum_{d \mid n}f(d)g(\frac{n}{d})

=ndnf(nd)g(d)= \sum_{\frac{n}{d} \mid n}f(\frac{n}{d})g(d)

=dnf(nd)g(d)= \sum_{d \mid n}f(\frac{n}{d})g(d)

=(gf)(n)= (g * f)(n)

结合律

(fg)h=f(gh)(f * g) * h = f * (g * h)

证明

((fg)h)(n)=xy=n(fg)(x)h(y)((f * g) * h)(n) = \sum_{xy=n}(f * g)(x)h(y)

=aby=n(fg)(ab)h(y)= \sum_{aby=n}(f * g)(ab)h(y)

=(ab)y=n(f(a)g(b))h(y)= \sum_{(a\cdot b)y=n}(f(a)g(b))h(y)

=a(by)=nf(a)(g(b)h(y))= \sum_{a(b \cdot y)=n}f(a)(g(b)h(y))

=(f(gh))(n)= (f * (g * h))(n)

分配律

(f+g)h=fh+gh(f+g)*h = f * h +g * h

证明

((f+g)h)(n)=dn(f+g)(d)h(nd)((f+g)*h)(n) = \sum_{d \mid n}(f + g)(d)h(\frac{n}{d})

=dnf(d)h(nd)+dng(d)h(nd)= \sum_{d \mid n}f(d)h(\frac{n}{d}) + \sum_{d \mid n} g(d)h(\frac{n}{d})

=(fh)(n)+(gh)(n)=(f * h)(n) + (g * h)(n)

性质 44

(xf)g=x(fg)      x为常数(xf)*g = x(f * g) \ \ \ \ \ \ x\text{为常数}

显然。

性质 55

f 和 g 均为积性函数,则 fg 为积性函数f \ \text{和} \ g\ \text{均为积性函数,则} \ f*g \ \text{为积性函数}

证明

(fg)(a)(fg)(b)=d1af(d1)g(ad1)d2bf(d2)g(bd2)(f*g)(a) \cdot (f * g)(b) = \sum_{d_1 \mid a}f(d_1)g(\frac{a}{d_1}) \cdot \sum_{d_2\mid b}f(d_2)g(\frac{b}{d_2})

=d1ad2bf(d1)g(ad1)f(d2)g(bd2)= \sum_{d_1 \mid a}\sum_{d_2\mid b}f(d_1)g(\frac{a}{d_1}) \cdot f(d_2)g(\frac{b}{d_2})

=d1d2abf(d1d2)g(abd1d2)= \sum_{d_1d_2 \mid ab}f(d_1d_2)g(\frac{ab}{d_1d_2})

=dabf(d)g(abd)= \sum_{d \mid ab}f(d)g(\frac{ab}{d})

=(fg)(ab)=(f*g)(ab)

特殊狄利克雷卷积

  1. Idk1=σkId_k * 1 = σ_k
  2. φ1=Id\varphi * 1 = Id
  3. 11=d1 * 1 = d
  4. μ1=ε\mu * 1 = \varepsilon

狄利克雷逆元

定义

如果 fg=εf* g = \varepsilonf(1)0f(1) \neq 0 ,则称 ggff 的狄利克雷逆元

求法

g(n)=1f(1)(εin,i1f(i)g(ni))g(n) = \frac{1}{f(1)}(\varepsilon - \sum_{i \mid n ,i \neq 1}f(i)g(\frac{n}{i}))

莫比乌斯函数

定义

μ(n)={1n=10n含有平方因子(1)kk 为 n的本质不同质因子个数\mu(n) = \begin{cases}1&n=1\\0&n\text{含有平方因子}\\ (-1)^k & k \ \text{为}\ n \text{的本质不同质因子个数}\end{cases}

性质

dnμ(d)=[n=1]\sum_{d \mid n} \mu (d) = [n = 1]

证明
n=i=1kpici,n=i=1kpin = \prod\limits_{i=1}^k p_i^{c_i},n'=\prod\limits_{i=1}^{k}p_i

那么有:

dnμ(d)=dnμ(d)=i=1kCki(1)i=(1+(1)k)=0k\sum_{d \mid n} \mu(d) = \sum_{d \mid n'}\mu(d)=\sum_{i = 1}^{k}C_k^i\cdot (-1)^i = (1 + (-1)^k) = 0^k

显然当且仅当 k=0k = 0n=1n = 1 时值为 11 , 否则为 00

这也证明了 μ1=ε\mu * 1 = \varepsilon

与欧拉函数的关系

dnμ(d)d=φ(n)n\sum_{d \mid n}\frac{\mu(d)}{d} = \frac{\varphi(n)}{n}

显然莫比乌斯函数是积性函数,所以可以线性筛:

void Get_Mu(int N) {
	Mu[1] = 1;
	for(int i = 2; i <= N; i++) {
		if(!Vis[i]) {
			Mu[i] = -1;
			Prime[++Cnt] = i;
		}
		for(int j = 1; j <= Cnt && i * Prime[j] <= N; j++) {
			Vis[i * Prime[j]] = true;
			if(i % Prime[j] == 0) break;
			else Mu[i * Prime[j]] = -Mu[i];
		}
	}
}

莫比乌斯反演

公式

dgcd(i,j)μ(d)=[gcd(i,j)=1]\sum\limits_{d \mid \gcd(i , j)} \mu (d) = [\gcd(i , j) = 1]

证明见上文性质。

例题选讲

[HAOI2011]Problem b

题意

i=xnj=ym[gcd(i,j)=k]       (1T,n,m,x,y5×104)\sum\limits_{i=x}^n \sum\limits_{j=y}^m [gcd(i , j) = k] \ \ \ \ \ \ \ (1 \le T , n , m , x , y \le 5 \times 10^4)

思路

我们浅浅的容斥一下,分成 44 块,每一块都为:

i=1nj=1m[gcd(i,j)=k]\sum\limits_{i=1}^n \sum\limits_{j=1}^m [gcd(i , j) = k]

替换下标得:

i=1nkj=1mk[gcd(i,j)=1]\sum\limits_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum\limits_{j=1}^{\lfloor \frac{m}{k} \rfloor} [gcd(i , j) = 1]

反演得:

i=1nkj=1mkdgcd(i,j)μ(d)\sum\limits_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum\limits_{j=1}^{\lfloor \frac{m}{k} \rfloor} \sum\limits_{d \mid \gcd(i , j)} \mu (d)

更换枚举顺序得:

d=1μ(d)i=1nk[di]j=1mk[dj]\sum\limits_{d = 1} \mu (d) \sum\limits_{i = 1} ^ {\lfloor \frac{n}{k} \rfloor} [d | i] \sum\limits_{j = 1} ^ {\lfloor \frac{m}{k} \rfloor} [d | j]

显然 1nk1 \sim \lfloor \frac{n}{k} \rfloordd 得倍数有 nkd\lfloor \frac{n}{kd} \rfloor 个,故原式化为:

d=1min(nk,mk)μ(d)nkdmkd\sum\limits_{d = 1}^{\min(\lfloor \frac{n}{k} \rfloor , \lfloor \frac{m}{k} \rfloor)} \mu (d) \lfloor \frac{n}{kd} \rfloor \lfloor \frac{m}{kd} \rfloor

然后就可以数论分块了。

思路
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50010;

inline void read(int &x)
{
    x=0;
    static int p;p=1;
    static char c;c=getchar();
    while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}
    while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();}
    x*=p;	
}

bool Vis[MAXN];
int Prime[MAXN] , Mu[MAXN] , Sum[MAXN] , Cnt , K , T;
int a , b , c , d;

void Get_Mu(int N) {
	Mu[1] = 1;
	for(int i = 2; i <= N; i++) {
		if(!Vis[i]) {
			Mu[i] = -1;
			Prime[++Cnt] = i;
		}
		for(int j = 1; j <= Cnt && i * Prime[j] <= N; j++) {
			Vis[i * Prime[j]] = true;
			if(i % Prime[j] == 0) break;
			else Mu[i * Prime[j]] = -Mu[i];
		}
	}
	for(int i = 1; i <= N; i++) Sum[i] = Sum[i - 1] + Mu[i];
}

long long Ans;

long long Solve (int a , int b) {
	Ans = 0;
	for(int l = 1 , r; l <= min(a , b); l = r + 1) {
		r = min(a / (a / l) , b / (b / l));
		Ans += (1ll * a / (1ll * l * K)) * (1ll * b / (1ll * l * K)) * (Sum[r] - Sum[l - 1]);
	}
	return Ans;
}


int main() {
	Get_Mu(50000);
	read(T);
	while(T--) {
		read(a);
		read(b);
		read(c);
		read(d);
		read(K);
		printf("%lld\n" ,Solve(b , d) - Solve(b , c - 1)  - Solve(a - 1 , d) + Solve(a - 1 , c - 1));
	}
	return 0;
}

YY的GCD

题意

i=1Nj=1M[gcd(i,j)prime]\sum\limits_{i=1}^N\sum\limits_{j = 1}^M [\gcd(i,j) \in prime]

思路

枚举质数得:

k=1Ni=1Nj=1M[gcd(i,j)=k]      (kprime)\sum\limits_{k = 1}^N\sum\limits_{i=1}^N\sum\limits_{j = 1}^M [\gcd(i,j) = k] \ \ \ \ \ \ (k \in prime)

同时除以 kk

k=1Ni=1Nkj=1Mk[gcd(i,j)=1]      (kprime)\sum\limits_{k = 1}^N\sum\limits_{i=1}^{\lfloor \frac{N}{k} \rfloor}\sum\limits_{j = 1}^{\lfloor \frac{M}{k} \rfloor} [\gcd(i,j) = 1] \ \ \ \ \ \ (k \in prime)

反演得

k=1Ni=1Nkj=1Mkdgcd(i,j)μ(d)      (kprime)\sum\limits_{k = 1}^N\sum\limits_{i=1}^{\lfloor \frac{N}{k} \rfloor}\sum\limits_{j = 1}^{\lfloor \frac{M}{k} \rfloor}\sum\limits_{d \mid \gcd(i,j)} \mu(d) \ \ \ \ \ \ (k \in prime)

同第一题,显然

k=1Nd=1Nkμ(d)×Nkd×Mkd      (kprime)\sum\limits_{k = 1}^N\sum\limits_{d = 1}^{\lfloor \frac{N}{k} \rfloor} \mu(d) \times \lfloor \frac{N}{kd} \rfloor \times \lfloor \frac{M}{kd} \rfloor \ \ \ \ \ \ (k \in prime)

T=kdT = kd ,得

k=1Nd=1Nkμ(d)×NT×MT      (kprime)\sum\limits_{k = 1}^N\sum\limits_{d = 1}^{\lfloor \frac{N}{k} \rfloor} \mu(d) \times \lfloor \frac{N}{T} \rfloor \times \lfloor \frac{M}{T} \rfloor \ \ \ \ \ \ (k \in prime)

枚举 TT

T=1NNT×MTkTμ(Tk)      (kprime)\sum\limits_{T = 1}^N \lfloor \frac{N}{T} \rfloor \times \lfloor \frac{M}{T} \rfloor \sum_{k \mid T}\mu(\lfloor \frac{T}{k}\rfloor)\ \ \ \ \ \ (k \in prime)

代码
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e7 + 10;

int T , N , M;

bool Vis[MAXN];
int Prime[MAXN] , Mu[MAXN] , Sum[MAXN] , Cnt , F[MAXN];

void Get_Mu(int N) {
	Mu[1] = 1;
	for(int i = 2; i <= N; i++) {
		if(!Vis[i]) {
			Mu[i] = -1;
			Prime[++Cnt] = i;
		}
		for(int j = 1; j <= Cnt && i * Prime[j] <= N; j++) {
			Vis[i * Prime[j]] = true;
			if(i % Prime[j] == 0) break;
			else Mu[i * Prime[j]] = -Mu[i];
		}
	}
	for(int i = 1; i <= Cnt; i++) {
		for(int j = 1; Prime[i] * j <= N; j++) {
			F[j * Prime[i]] += Mu[j];
		}
	}
	for(int i = 1; i <= N; i++) Sum[i] = Sum[i - 1] + F[i];
}

long long AC(int a , int b) {
	long long Ans = 0;
	for(int l = 1 , r = 0; l <= a; l = r + 1) {
		r = min(a / (a / l) , b / (b / l));
		Ans += (long long)(Sum[r] - Sum[l - 1]) * (long long)(a / l) * (long long)(b / l);
	}
	return Ans;
}

int main() {
	ios::sync_with_stdio(false);
	
	Get_Mu(MAXN - 10);
	
	cin >> T;
	
	while(T--) {
		cin >> N >> M;
		cout << AC(min(N , M) , max(N , M)) << endl;
	}
	
	return 0;
}

[SDOI2015]约数个数和

d(ij)=xiyy[gcd(x,y)=1]d(ij) = \sum\limits_{x \mid i} \sum\limits_{y \mid y} [gcd(x , y) = 1]