从积性函数到莫比乌斯反演

本文最后更新于:2022年10月5日 下午

从积性函数到莫比乌斯反演

呜呜呜,为了数论课不做大牢,学数论!

简单介绍

数论函数

数论函数,简单来说就是定义域是\(\mathbb{N^{*}}\)的函数,可以视为一个数列

积性函数

定义

积性函数是一类特殊的数论函数,它满足以下性质 \[ f(1) = 1.\ \forall i, j\in\mathbb{N^{*}},gcd(i,j)=1: f(i*j)=f(i)*f(j) \] 特别的

若积性函数被称为完全积性函数,若它满足以下性质 \[ \forall i,j\in \mathbb{N^{*}}:f(i*j)=f(i)*f(j) \]

性质

\(f\),\(g\)为积性函数,则 \[ h(x)=f(x)*g(x),\ h(x)=f(x^{p}),\ h(x)=f^{p}(x),\ h(x)=\sum_{d|x}f(d)g(\frac{x}{d}) \] 也为积性函数

特别的,根据唯一分解定理,设\(x=\prod p_i^{k_i}\),若\(F\)为积性函数,则有 \[ F(x)=\prod F(p_i^{k_i}) \]\(F\)为完全积性函数,则有 \[ F(x)=\prod F^{k_i}(p_i) \]

例子

恒等函数\(id(n) \equiv n\)

单位函数\(\epsilon (n)=[n=1]\)

常数函数\(1(n)\equiv 1\)

因子和函数\(\delta(n)=\sum_{d|n}d\)

因子个数函数\(\tau(n)=\sum_{d|n}1\)

一般的,除数函数\(\sigma_k(n)=\sum_{d|n}d^k\)

欧拉函数\(\phi(n)=\sum_{i=1}^n[gcd(i,n)=1]\),即\(n\)的与\(n\)互质的因数的个数

莫比乌斯函数,其中\(n=\prod_{i=1}^r p_i^{k_i}\) \[ \mu(n)=\begin{cases} 1,n=1\\ 0,\exists i, s.t.k_i>=2\\ (-1)^r,otherwise \end{cases} \] 值得指出的是,上述前三个函数为完全积性函数

\(Dirichlet\)卷积

定义

\(f\)\(g\)为数论函数,则两者的\(Dirichlet\)卷积\(f*g\)定义如下 \[ f*g(n):=\sum_{d|n}f(d)g(\frac{n}{d}) \]

性质

\(f\),\(g\),\(h\)为数论函数

单位元存在性

\(\forall f, \exists \epsilon :f*\epsilon \equiv f\)

逆元唯一性

\(\exists g, s.t.f*g\equiv\epsilon\),则称\(g\)\(f\)的逆元,事实上,逆元唯一

交换律

\(f*g=g*f\)

结合律

\(f*(g*h)=(f*g)*h\)

分配律

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

恒等关系

\(f=g\iff f*h=g*h\)

重要结论

1.积性函数的卷积仍为积性函数

2.积性函数的逆元也为积性函数

例子

1.\(\epsilon=\mu*1\)

2.\(\tau=1*1\)

3.\(\delta=id*1\)

4.\(\phi=\mu*n\)

数论分块

数论分块可以用于快速求解带向下取整(显然也有整除)的和式,时间复杂度可以达到\(O(\sqrt n)\)

两个结论

1.\(\forall a,b,c\in\mathbb{Z}, \lfloor\frac{\lfloor\frac{a}{b}\rfloor}{c}\rfloor=\lfloor\frac{a}{bc}\rfloor\)

2.\(\forall n\in\mathbb{N^*},|V|=\{\lfloor\frac{n}{d}\rfloor|\forall d, 1 \le d\le n\}| \le 2\lfloor\sqrt{n}\rfloor\)

所以可以枚举每个整数\(d\)对应的\(i\)的区间,来分块计算各个小区间对应的答案,最后相加就行,实现如下

实现

1
2
3
4
5
6
7
8
9
10
ll partitioning(ll n) {
ll ans = 0;
ll l, r;
for(l = 1; l <= n; l++) {
r = n / (n / l);
ans += 1LL * (r - l + 1) * expression(l);\\expression is the formula that is to be solved
l = r;
}
return ans;
}

莫比乌斯反演

来到了,高一集训时的噩梦,\(cjq\)大仙的解方程猜测\(\mu\)函数现场,四年来念念不忘的Mobius Inversion

\(\mu\)函数的补充

\([gcd(i,j)=1]=\sum_{d|gcd(i,j)} {\mu(d)}\)

\([gcd(i,j)=1]=\epsilon *gcd(i,j)\)

显然,如果\(gcd(i,j)=1\),那么d只能取\(1\),故和式为\(1\);若不然,\(gcd(i,j)\)的因子总是成对出现,故可取到的\(\mu\)\((-1)^r\)\(r\)总是连续的\(1-2n\),故结果为\(0\)

线性筛

线性筛可以用于求绝大部分积性函数(其实我也不知道有什么不能求的),区别只在于在线性筛过程中对函数值的处理计算

对于\(\mu\)函数,实现如下

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void getMu() {
mu[1] = 1;
inp[1] = 1;
for(int i = 2; i <= maxn; i++) {
if(!inp[i]) prime[++tot] = i, mu[i] = -1;
for(int j = 1; j <= tot && i * prime[j] <= maxn; j++) {
inp[i * prime[j]] = 1;
if(i % prime[j] == 0) {
mu[i * p[j]] = 0;
break;
}
mu[i * p[j]] = -mu[i];
}
}
}

结论

\(f\)\(g\)为两个数论函数,若 \[ f(n)=\sum_{d|n}g(d) \] 则有 \[ g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d}) \] \(f\)称为\(g\)的莫比乌斯变换,\(而g\)称为\(f\)的莫比乌斯反演,可以看出,\(f = g*1\)

那么,如果遇到 \[ \sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=1] \] 就可以转化为 \[ \sum_{i=1}^n\sum_{j=1}^m\sum_{d|gcd(i,j)}{\mu(d)} \] 改变求和顺序,可以得到 \[ \sum_{d=1}\mu(d)\sum_{i = 1}^n[d|i]\sum_{j=1}^m[d|j] \] 显然后面两个求和号可以直接得出结果,故 \[ \sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=1]=\sum_{d=1}^{min(n,m)}\mu(d)\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor \] 直接使用数论分块解决即可

实现

[HAOI2011] Problem b为例

推导与上述无异,再使用二维容斥即可解决问题

即计算 \[ \sum_{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 \]\(n=b,m=d;n=b,m=c-1;n=a-1,m=d;n=a-1,m=c-1\)四种情况即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int n, mu[maxn], prime[maxn], tot = 0;
bool inp[maxn];
int a, b, c, d, k;

void init() { //get prefix of mu
mu[1] = 1, inp[1] = 1;
rep(i, 2, maxn) {
if(!inp[i]) {
prime[++tot] = i;
mu[i] = -1;
}
for(int j = 1; j <= tot && i * prime[j] <= maxn; j++) {
inp[i * prime[j]] = 1;
if(i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
}
mu[i * prime[j]] = -mu[i];
}
}
rep(i, 1, maxn) mu[i] += mu[i - 1];
}

ll cal(int n, int m) { //calculate the sum
ll ans = 0;
ll l, r;
for(l = 1; l <= min(n, m); l++) {
r = min(n / (n / l), m / (m / l));
ans += 1LL * (mu[r] - mu[l - 1]) * (n / l) * (m / l);
l = r;
}
return ans;
}

void solve() {
a = read(), b = read(), c = read(), d = read(), k = read();
ll res = cal(b / k, d / k) - cal((a - 1) / k, d / k) - cal(b / k, (c - 1) / k) + cal((a - 1) / k, (c - 1) / k);
printf("%lld\n", res);
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!