发表于 | 分类于 | 0 | 阅读次数 1584

狄利克雷卷积

符号即约定

  • [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) 是定义在数论函数间的一种二元运算，可以定义为：

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

⇒∑d∣nf(d)g(nd)\Rightarrow\sum_{d \mid n}f(d)g(\frac{n}{d})

性质

交换律

f∗g=g∗ff*g = g*f

证明

(f∗g)(n)=∑d∣nf(d)g(nd)(f*g)(n) = \sum_{d \mid n}f(d)g(\frac{n}{d})

=∑nd∣nf(nd)g(d)= \sum_{\frac{n}{d} \mid n}f(\frac{n}{d})g(d)

=∑d∣nf(nd)g(d)= \sum_{d \mid n}f(\frac{n}{d})g(d)

=(g∗f)(n)= (g * f)(n)

结合律

(f∗g)∗h=f∗(g∗h)(f * g) * h = f * (g * h)

证明

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

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

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

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

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

分配律

(f+g)∗h=f∗h+g∗h(f+g)*h = f * h +g * h

证明

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

=∑d∣nf(d)h(nd)+∑d∣ng(d)h(nd)= \sum_{d \mid n}f(d)h(\frac{n}{d}) + \sum_{d \mid n} g(d)h(\frac{n}{d})

=(f∗h)(n)+(g∗h)(n)=(f * h)(n) + (g * h)(n)

性质 44

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

显然。

性质 55

f 和 g 均为积性函数，则 f∗g 为积性函数f \ \text{和} \ g\ \text{均为积性函数，则} \ f*g \ \text{为积性函数}

证明

(f∗g)(a)⋅(f∗g)(b)=∑d1∣af(d1)g(ad1)⋅∑d2∣bf(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})

=∑d1∣a∑d2∣bf(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})

=∑d1d2∣abf(d1d2)g(abd1d2)= \sum_{d_1d_2 \mid ab}f(d_1d_2)g(\frac{ab}{d_1d_2})

=∑d∣abf(d)g(abd)= \sum_{d \mid ab}f(d)g(\frac{ab}{d})

=(f∗g)(ab)=(f*g)(ab)

特殊狄利克雷卷积

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

狄利克雷逆元

定义

如果 f∗g=εf* g = \varepsilon 且 f(1)≠0f(1) \neq 0 ，则称 gg 是 ff 的狄利克雷逆元

求法

g(n)=1f(1)(ε−∑i∣n,i≠1f(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}

性质

∑d∣nμ(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

那么有:

∑d∣nμ(d)=∑d∣n′μ(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 = 0 即 n=1n = 1 时值为 11 ， 否则为 00

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

与欧拉函数的关系

∑d∣nμ(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];
		}
	}
}

莫比乌斯反演

公式

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

证明见上文性质。

例题选讲

[HAOI2011]Problem b

题意

求

∑i=xn∑j=ym[gcd(i,j)=k]       (1≤T,n,m,x,y≤5×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=1n∑j=1m[gcd(i,j)=k]\sum\limits_{i=1}^n \sum\limits_{j=1}^m [gcd(i , j) = k]

替换下标得：

∑i=1⌊nk⌋∑j=1⌊mk⌋[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=1⌊nk⌋∑j=1⌊mk⌋∑d∣gcd⁡(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=1⌊nk⌋[d∣i]∑j=1⌊mk⌋[d∣j]\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]

显然 1∼⌊nk⌋1 \sim \lfloor \frac{n}{k} \rfloor 中 dd 得倍数有 ⌊nkd⌋\lfloor \frac{n}{kd} \rfloor 个，故原式化为：

∑d=1min⁡(⌊nk⌋,⌊mk⌋)μ(d)⌊nkd⌋⌊mkd⌋\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=1N∑j=1M[gcd⁡(i,j)∈prime]\sum\limits_{i=1}^N\sum\limits_{j = 1}^M [\gcd(i,j) \in prime]

思路

枚举质数得：

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

同时除以 kk 得

∑k=1N∑i=1⌊Nk⌋∑j=1⌊Mk⌋[gcd⁡(i,j)=1]      (k∈prime)\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=1N∑i=1⌊Nk⌋∑j=1⌊Mk⌋∑d∣gcd⁡(i,j)μ(d)      (k∈prime)\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=1N∑d=1⌊Nk⌋μ(d)×⌊Nkd⌋×⌊Mkd⌋      (k∈prime)\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=1N∑d=1⌊Nk⌋μ(d)×⌊NT⌋×⌊MT⌋      (k∈prime)\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=1N⌊NT⌋×⌊MT⌋∑k∣Tμ(⌊Tk⌋)      (k∈prime)\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)=∑x∣i∑y∣y[gcd(x,y)=1]d(ij) = \sum\limits_{x \mid i} \sum\limits_{y \mid y} [gcd(x , y) = 1]

  • 本文作者： CmsMartin
  • 本文链接： /archives/mu
  • 版权声明： 本博客所有文章除特别声明外，均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处！