0%

莫比乌斯反演

数论函数

数论函数: 定义域为正整数的函数。

积性函数: 对于任意两个互质的正整数 $a, b$,均满足 $f(ab)=f(a)\times f(b)$ 的函数 $f$

完全积性函数: 对于所有正整数 $a, b$,均满足 $f
(ab)=f(a)\times f(b)$ 的函数 $f$

对于一个积性函数 $f$,$f(n)=f(\prod p_i^{a_i})=\prod f(p_i^{a_i})$,若 $f$ 还满足完全积性,则 $f(n)=\prod f(p_i)^{a_i}$

常见积性函数

欧拉函数 $\varphi(n)$

莫比乌斯函数 $\mu(n)$: 若 $n$ 有平方数因子,则 $\mu(n)=0$。否则若 $n$ 为 $k$ 个不同质数之积,则 $\mu(n)=(-1)^k$。

除数函数: $\sigma_k(n)$ 表示 $n$ 的所有正因子的 $k$ 次幂之和。

$d(n)=\sigma_0(n)$ 表示 $n$ 的正因子个数,$\sigma(n)=\sigma_1(n)$ 表示 $n$ 的所有正因子之和。

幂函数: $\operatorname{Id}_k(n)=n^k$,$1(n)=\operatorname{Id}_0(n)=1$,$\operatorname{Id}(n)=\operatorname{Id}_1(n)=n$

单位函数:
$e(n)=\varepsilon(n)=
\begin{cases}
1 & n = 1\\
0 & n > 1
\end{cases}
$

狄利克雷(Dirichlet)卷积

定义两个数论函数 $f$,$g$ 的 Dirichlet 卷积:

狄利克雷卷积的性质

交换律:

结合律:

分配律:

单位元:

常见的狄利克雷卷积

  • $d(n)=\sum_{d|n}1$,即 $d=1*1$

  • $\sigma(n)=\sum_{d|n}d$,即 $\sigma=d*1$

  • $\varphi(n)=\sum_{d|n}\mu(d)\frac{n}{d}$,即 $\varphi=\mu*\operatorname{Id}$

  • $\varepsilon(n)=\sum_{d|n}\mu(d)$,即 $\varepsilon=\mu*1$

一些结论和证明

$n = \sum_{d|n}\varphi(d)$。

$1$ 到 $n$ 中与 $n(n>1)$ 互质的数的和为 $\dfrac{n\times \varphi(n)}{2}$。

$\varepsilon=\mu*1$ 即为 $\sum_{d|n}\mu(d)=[n=1]$。

证明:$n=1$ 时 $\sum_{d|n}\mu(d)=1$。

$n \neq 1$ 时,设 $n$ 有 $k$ 个质因子,只有当 $n$ 的因子中所有质因子次数都为 $1$ 时,$\mu$ 不为 $0$,即

因此 $\sum_{d|n}\mu(d)=[n=1]$。

莫比乌斯反演

若两个函数 $f$,$g$ 满足:

则它们也满足

反之亦然,即

它的另一个形式:

线性筛

反演的题目经常会需要快速求积性函数,这时就要用到线性筛。

线性筛质数

设 $pr_i$ 表示 $i$ 的最小质因子。枚举所有不超过 $pr_i$ 的质数 $p$,使 $pr_(i\cdot p) = p$,相当于将每个数的质因子降序分解,每个数只会被它的最小质因子筛一次,因此复杂度是 $O(n)$ 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Shaker(int x)
{
for (int i = 2; i <= x; i++)
{
if (!pr[i]) prime[++cnt] = pr[i] = i;
for (int j = 1; j <= cnt; j++)
{
int k = i * prime[j];
if (k > x) break;
pr[k] = prime[j];
if (i % prime[j] == 0) break;
}
}
}

线性筛积性函数

利用线性筛求解每个数 $n$ 的最小质因子 $p$ 的次数 $k$:令 $n = pm$,由于 $p$ 是 $n$ 最小的质因子,若 $p^2 | n$
,则 $p | m$ ,并且 $p$ 也是 $m$ 最小的质因子,这样在筛法的同时即可算出新筛去的合数的最小质因子的次数。

这样在求解积性函数时,我们能利用 $f(n)=f(p^k)f(\frac{n}{p^k})$,在线性筛的同时快速求出 $f(n)$。

线性筛欧拉函数

$\varphi(p^k)=(p-1)p^{k-1}$,因此筛法时,若 $p | m$,$\varphi$ 就乘上 $p$,否则乘上 $p-1$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Shaker(int x)
{
phi[1] = 1;
for (int i = 2; i <= x; i++)
{
if (!pr[i]) prime[++cnt] = pr[i] = i, phi[i] = i - 1;
for (int j = 1; j <= cnt; j++)
{
int k = i * prime[j];
if (k > x) break;
pr[k] = prime[j];
if (i % prime[j] == 0)
{
phi[k] = phi[i] * prime[j];
break;
}
phi[k] = phi[i] * (prime[j] - 1);
}
}
}

线性筛莫比乌斯函数

只有当 $k=1$ 时 $\mu(p^k)=-1$,否则 $\mu(p^k)=0$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Shaker(int x)
{
mu[1] = 1;
for (int i = 2; i <= x; i++)
{
if (!pr[i]) prime[++cnt] = pr[i] = i, mu[i] = -1;
for (int j = 1; j <= cnt; j++)
{
int k = i * prime[j];
if (k > x) break;
pr[k] = prime[j];
if (i % prime[j] == 0)
{
mu[k] = 0;
break;
}
mu[k] = -mu[i];
}
}
}

筛法求约数个数、约数和

约数个数 $d_i$ 是积性函数,因此也可以用筛法求。类似的可以求约数和、最小质因子 $k$ 次幂的和。

求约数个数。$num_i$ 表示 $i$ 的最小质因子出现次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void Shaker(int x)
{
d[1] = 1;
for (int i = 2; i <= x; i++)
{
if (!pr[i]) prime[++cnt] = pr[i] = i, d[i] = 2, num[i] = 1;
for (int j = 1; j <= cnt; j++)
{
int k = i * prime[j];
if (k > x) break;
pr[k] = prime[j];
if (i % prime[j] == 0)
{
num[k] = num[i] + 1;
d[k] = d[i] / num[k] * (num[k] + 1);
break;
}
num[k] = 1;
d[k] = d[i] * 2;
}
}
}

求约数和。$f_i$ 表示 $i$ 的约数和,$g_i$ 表示 $i$ 的最小质因子的 $p^0+p^1+p^2+\cdots +p^k$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void Shaker(int x)
{
g[1] = f[1] = 1;
for (int i = 2; i <= x; i++)
{
if (!pr[i]) prime[++cnt] = pr[i] = i, g[i] = f[i] = i + 1;
for (int j = 1; j <= cnt; j++)
{
int k = i * prime[j];
if (k > x) break;
pr[k] = prime[j];
if (i % prime[j] == 0)
{
g[k] = g[i] * prime[j] + 1;
f[k] = f[i] / g[i] * g[k];
break;
}
g[k] = prime[j] + 1;
f[k] = f[i] * f[prime[j]];
}
}
}

题目

BZOJ 2705

$F$ 是积性函数,因此直接 $O(\sqrt n)$ 质因数分解得到答案。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL n, ans = 1;

void Factor(LL x)
{
for (LL i = 2; i * i <= x; i++)
{
if (x % i == 0)
{
LL p = i, k = 0, res = 1;
while (x % i == 0) x /= i, k++, res *= p;
ans *= res + k * (p - 1) * res / p;
}
}
if (x > 1) ans *= x + (x - 1);
}

int main()
{
cin >> n;
Factor(n);
cout << ans << endl;
return 0;
}

BZOJ 2226

$\sum_{d|n}d\cdot \varphi(d)$ 是积性函数,因此可以线性筛 $O(n)$ 预处理,单次询问 $O(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
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1000000 + 5;

int prime[N], pr[N], cnt;
LL f[N], g[N];

void Shaker(int x)
{
f[1] = 1;
for (int i = 2; i <= x; i++)
{
if (!pr[i])
{
prime[++cnt] = pr[i] = i;
g[i] = i;
f[i] = (i - 1) * g[i] + 1;
}
for (int j = 1; j <= cnt; j++)
{
int k = i * prime[j];
if (k > x) break;
pr[k] = prime[j];
if (i % prime[j] == 0)
{
g[k] = g[i] * prime[j] * prime[j] + prime[j];
f[k] = f[i] / ((prime[j] - 1) * g[i] + 1) * ((prime[j] - 1) * g[k] + 1);
break;
}
g[k] = prime[j];
f[k] = f[i] * ((prime[j] - 1) * g[k] + 1);
}
}
}

int main()
{
Shaker(1000000);
int T;
scanf("%d", &T);
while (T--)
{
LL n;
scanf("%lld", &n);
printf("%lld\n", n * (f[n] + 1) / 2);
}
return 0;
}

Luogu P1447

除法分块,$O(\sqrt n)$。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
#define fl first
#define fr second
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 100000 + 5;

LL sum[N];
int prime[N], pr[N], phi[N], cnt;

void Shaker(int x)
{
phi[1] = 1;
for (int i = 2; i <= x; i++)
{
if (!pr[i]) prime[++cnt] = pr[i] = i, phi[i] = i - 1;
for (int j = 1; j <= cnt; j++)
{
int k = i * prime[j];
if (k > x) break;
pr[k] = prime[j];
if (i % prime[j] == 0)
{
phi[k] = phi[i] * prime[j];
break;
}
phi[k] = phi[i] * (prime[j] - 1);
}
}
for (int i = 1; i <= x; i++) sum[i] = sum[i - 1] + phi[i];
}

inline LL F(LL n, LL m)
{
LL res = 0;
for (register LL l = 1, r; l <= min(n, m); l = r + 1)
{
r = min(n / (n / l), m / (m / l));
res += (sum[r] - sum[l - 1]) * (n / l) * (m / l);
}
return res;
}

int main()
{
Shaker(N - 5);
int n, m;
cin >> n >> m;
cout << F(n, m) * 2 - 1LL * n * m << endl;
return 0;
}

Luogu P1829

我们令

$G(n,m)$,$F(n,m)$ 都可以除法分块求,时间复杂度 $O(n)$。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#define fl first
#define fr second
#define pb push_back
#define mp make_pair
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 1e7 + 5;
const int mod = 20101009;

LL sum[N];
int prime[N], pr[N], mu[N], cnt;

inline LL ch(LL x)
{
return (x % mod + mod) % mod;
}

void Shaker(int x)
{
mu[1] = 1;
for (int i = 2; i <= x; i++)
{
if (!pr[i]) prime[++cnt] = pr[i] = i, mu[i] = -1;
for (int j = 1; j <= cnt; j++)
{
int k = i * prime[j];
if (k > x) break;
pr[k] = prime[j];
if (i % prime[j] == 0)
{
mu[k] = 0;
break;
}
mu[k] = -mu[i];
}
}
for (int i = 1; i <= x; i++) sum[i] = ch(sum[i - 1] + 1LL * mu[i] * i * i % mod);
}

inline LL Sum(LL n)
{
return ch(n * (n + 1) / 2 % mod);
}

inline LL G(LL n, LL m)
{
LL res = 0;
for (LL l = 1, r; l <= min(n, m); l = r + 1)
{
r = min(n / (n / l), m / (m / l));
res = ch(res + ch(sum[r] - sum[l - 1] + mod) * Sum(n / l) % mod * Sum(m / l) % mod);
}
return res;
}

inline LL F(LL n, LL m)
{
LL res = 0;
for (LL l = 1, r; l <= min(n, m); l = r + 1)
{
r = min(n / (n / l), m / (m / l));
res = ch(res + (r - l + 1) * (l + r) / 2 % mod * G(n / l, m / l) % mod);
}
return res;
}

int main()
{
Shaker(10000000);
LL n, m;
cin >> n >> m;
cout << F(n, m) << endl;
return 0;
}

Luogu P2257

方法一:这题主要难处理的是 $[\gcd(i,j)\in primes]$,如果我们有一个 $f$,使得 $\sum_{d|n}f(d)=[n\in primes]$ 就比较好了。 $f$ 容易用反演的套路 $O(n\log n)$ 递推出来。

方法二:

根据套路,我们枚举 $k=pd$,

可以线性筛求出 $\mu$,然后 $O(n\log n)$ 枚举因数求出 $\sum_{p\in primes}\mu(\frac{k}{p})$ 的前缀和。

Luogu P3327

其中 $d(x)$ 表示 $x$ 的约数个数。

这题只需要知道

即可,剩下的都是套路了。

另外,还有一个与这相似的式子:

原理与上面类似,都是对于每个质因子,它的幂在 $x$ 或 $y$ 上是 $0$,于是便能取到所有的幂。

杜教筛

原理

杜教筛可以处理数论函数前缀和问题。

对于数论函数 $f$,想要计算 $S(n)=\sum_{i=1}^nf(i)$。

对于任意一个数论函数 $g$,一定满足

证明:

就是交换了下求和顺序,然后把枚举 $i$ 变成了枚举 $\frac{i}{d}$。

那么就可以得到递推式

假如我们可以快速对 $\sum_{i=1}^n(f\ast g)(i)$ 求和,并用数论分块求解 $\sum_{i=2}^n g(i)S\left(\left\lfloor \frac{n}{i}\right\rfloor\right)$,就可以在较短时间内求得 $g(1)S(n)$。

莫比乌斯函数前缀和

我们知道,$\epsilon =\mu \ast 1$,即 $\epsilon(n)=\sum_{d \mid n} \mu(d)$。

因此,$S(n)=\sum_{i=1}^n \epsilon(i)-\sum_{i=2}^n S(\lfloor \frac{n}{i}\rfloor)=1-\sum_{i=2}^n S(\lfloor \frac{n}{i}\rfloor)$。

用线性筛预处理出前 $n^{\frac{2}{3}}$ 项,剩余部分用整除分块计算,总时间复杂度为 $O(n^{\frac{2}{3}})$。

欧拉函数前缀和

直接用莫比乌斯反演:

对于 $\sum_{i=1}^n \sum_{j=1}^i 1[\gcd(i,j)=1]$,排除掉 $i=1,j=1$ 的情况,再将结果除以 $2$ 即可。

当然也可以用杜教筛,$\varphi\ast 1=ID$

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 2000000 + 5;

int prime[N], pr[N], mu[N], sum[N], cnt;
map<LL, LL> Mu;

void Shaker(int x)
{
mu[1] = 1;
for (int i = 2; i <= x; i++)
{
if (!pr[i]) prime[++cnt] = pr[i] = i, mu[i] = -1;
for (int j = 1; j <= cnt; j++)
{
int k = i * prime[j];
if (k > x) break;
pr[k] = prime[j];
if (i % prime[j] == 0)
{
mu[k] = 0;
break;
}
mu[k] = -mu[i];
}
}
for (int i = 1; i <= x; i++) sum[i] = sum[i - 1] + mu[i];
}

LL Get_mu(LL x)
{
if (x <= N - 5) return sum[x];
if (Mu[x]) return Mu[x];
LL res = 1;
for (LL i = 2, j; i <= x; i = j + 1)
{
j = x / (x / i);
res -= Get_mu(x / i) * (j - i + 1);
}
return Mu[x] = res;
}

LL Get_phi(LL x)
{
LL res = 0;
for (LL i = 1, j; i <= x; i = j + 1)
{
j = x / (x / i);
res += (Get_mu(j) - Get_mu(i - 1)) * (x / i) * (x / i);
}
return (res - 1) / 2 + 1;
}

int main()
{
Shaker(N - 5);
int T;
scanf("%d", &T);
while (T--)
{
LL n;
scanf("%lld", &n);
printf("%lld %lld\n", Get_phi(n), Get_mu(n));
}
return 0;
}

P3768 简单的数学题

先将其化为

现在我们想求 $f(n)=n^2\varphi(n)$ 的前缀和,于是我们尝试构造 $g$,使 $f\ast g$ 和 $g$ 能够快速求和。

给 $f$ 卷上 $ID^2$,化简一下,得到

再化一下 $S(n)$

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
const int N = 5e6 + 5;

int prime[N], phi[N], cnt;
LL sum[N], n, p, inv2, inv6;
unordered_map<LL, LL> Map;
bool pr[N];

void Shaker(int x)
{
phi[1] = 1;
for (int i = 2; i <= x; i++)
{
if (!pr[i]) prime[++cnt] = i, pr[i] = 1, phi[i] = i - 1;
for (int j = 1; j <= cnt; j++)
{
int k = i * prime[j];
if (k > x) break;
pr[k] = 1;
if (i % prime[j] == 0)
{
phi[k] = phi[i] * prime[j];
break;
}
phi[k] = phi[i] * (prime[j] - 1);
}
}
for (int i = 1; i <= x; i++) sum[i] = (sum[i - 1] + 1LL * i * i % p * phi[i]) % p;
}

LL qpow(LL a, LL b)
{
LL res = 1;
for (; b; b >>= 1, a = a * a % p)
if (b & 1) res = res * a % p;
return res;
}

LL Inv(LL x)
{
return qpow(x, p - 2);
}

LL Get_Sum2(LL x)
{
x %= p;
return x * (x + 1) % p * (x * 2 + 1) % p * inv6 % p;
}

LL Get_Sum3(LL x)
{
x %= p;
return x * (x + 1) % p * inv2 % p * x % p * (x + 1) % p * inv2 % p;
}

LL S(LL x)
{
if (x <= N - 5) return sum[x];
if (Map[x]) return Map[x];
LL res = Get_Sum3(x);
for (LL l = 2, r; l <= x; l = r + 1)
{
r = x / (x / l);
res = (res - (Get_Sum2(r) - Get_Sum2(l - 1)) % p * S(x / l)) % p;
}
return Map[x] = (res + p) % p;
}

LL Solve(LL x)
{
LL res = 0;
for (LL l = 1, r; l <= x; l = r + 1)
{
r = x / (x / l);
res = (res + Get_Sum3(x / l) * (S(r) - S(l - 1)) % p) % p;
}
return (res + p) % p;
}

int main()
{
scanf("%lld%lld", &p, &n);
Shaker(N - 5);
inv2 = Inv(2), inv6 = Inv(6);
printf("%lld\n", Solve(n));
return 0;
}