莫比乌斯反演习题总结

Foreword

题目 + 题解

$(i, j) \Longleftrightarrow \gcd (i, j)$

[SDOI2017] 数字表格

Description

$$
T \le 10 ^3, 1 \le n, m \le 10 ^6
$$

Solution

不妨设 $n \le m$
$$
\begin{aligned}
& \prod _{i = 1} ^n \prod _{j = 1} ^m f((i, j)) \\
=& \prod _{d = 1} ^n \prod _{i = 1} ^n \prod _{j = 1} ^m [(i, j) = d] f(d) \\
=& \prod _{d = 1} ^n f(d) ^{\sum _{i = 1} ^n \sum _{j = 1} ^m [(i, j) = d]} \\
\end{aligned}
$$
指数部分提出来 单独计算
$$
\begin{aligned}
& \sum _{i = 1} ^n \sum _{j = 1} ^m [(i, j) = d] \\
=& \sum _{i = 1} ^{\lfloor \frac n d \rfloor} \sum _{j = 1} ^{\lfloor \frac m d \rfloor} [(i, j) = 1] \\
=& \sum _{i = 1} ^{\lfloor \frac n d \rfloor} \sum _{j = 1} ^{\lfloor \frac m d \rfloor} \sum _{x | (i, j)} \mu (x) \\
=& \sum _{x = 1} ^{\lfloor \frac n d \rfloor} \mu (x) \lfloor \frac n {dx} \rfloor \lfloor \frac m {dx} \rfloor
\end{aligned}
$$

考虑先枚举 $dx$ 的乘积再枚举 $d$ ,可以证明这样得出的答案不变(简易理解就是可以遍历到所有可能的 $d, x$ 的取值集合,不重不漏)

这应该也算是一种套路了

令 $T = dx$ ,$x$ 可用 $\frac T d$ 代替
$$
\begin{aligned}
& \prod _{T = 1} ^n \prod _{d | T} f(d) ^{\mu (\frac T d) \lfloor \frac n T \rfloor \lfloor \frac m T \rfloor} \\
=& \prod _{T = 1} ^n \left( \prod _{d | T} f(d) ^{\mu (\frac T d) } \right) ^{ \lfloor \frac n T \rfloor \lfloor \frac m T \rfloor}
\end{aligned}
$$
预处理 斐波那契数列及其逆元 和 里面东西的前缀积,筛出 $\mu$ 之后直接枚举每个数对其倍数算贡献,复杂度 $\cal O(n (\ln n + \log))$ ( $\log$ 是快速幂带的复杂度,这里 $\mu$ 只有三种取值,预处理逆元后就不需要快速幂了)

每次询问数论分块 + 快速幂,复杂度 $\cal O(T (\sqrt n + \sqrt m) \log)$ ,其中 $\cal T$ 是数据组数(注意逆元)

Code

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
/**********************************************************
* Author : EndSaH
* Email : hjxhb1@gmail.com
* Created Time : 2019-05-31 21:11
* FileName : SDOI2017_shuzibiaoge.cpp
* Website : https://endsah.cf
* *******************************************************/

#include <cstdio>
#include <cctype>
#include <cmath>
#include <vector>
#include <bitset>

typedef long long LL;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The message in line %d, Function %s: %s\n", __LINE__, __FUNCTION__, s)
#define getchar() (ipos == iend and (iend = (ipos = _ibuf) + fread(_ibuf, 1, __bufsize, stdin), ipos == iend) ? EOF : *ipos++)
#define putchar(ch) (opos == oend ? fwrite(_obuf, 1, __bufsize, stdout), opos = _obuf : 0, *opos++ = (ch))
#define __bufsize (1 << 21 | 1)

char _ibuf[__bufsize], _obuf[__bufsize], _stk[20];
char *ipos = _ibuf, *iend = _ibuf, *opos = _obuf, *oend = _obuf + __bufsize, *stkpos = _stk;

struct END
{ ~END() { fwrite(_obuf, 1, opos - _obuf, stdout); } }
__;

inline int read()
{
register int x = 0;
register char ch;
while (!isdigit(ch = getchar()));
while (x = (x << 3) + (x << 1) + (ch & 15), isdigit(ch = getchar()));
return x;
}

template <typename _INT>
inline void write(_INT x)
{
while (*++stkpos = x % 10 ^ 48, x /= 10, x);
while (stkpos != _stk)
putchar(*stkpos--);
}

template <typename _Tp>
inline bool Chkmax(_Tp& x, const _Tp& y)
{ return x < y ? x = y, true : false; }

template <typename _Tp>
inline bool Chkmin(_Tp& x, const _Tp& y)
{ return x > y ? x = y, true : false; }

const int maxN = 1e6 + 2;
const int mod = 1e9 + 7;

int T, n, m;
int mu[maxN], fib[maxN], fibinv[maxN], F[maxN];
std::bitset<maxN> vis;
std::vector<int> prim;

inline void Mod(int& x)
{ x >= mod ? x -= mod : 0; }

inline int QP(int a, LL n)
{
if (n == -1)
return QP(a, mod - 2);
if (a == 1)
return 1;
register int res = 1;
while (n)
{
if (n & 1)
res = (LL)res * a % mod;
a = (LL)a * a % mod;
n >>= 1;
}
return res;
}

inline void Pre(int n)
{
fib[1] = fibinv[1] = mu[1] = F[1] = F[0] = 1;
for (register int i = 2; i <= n; ++i)
{
F[i] = 1, Mod(fib[i] = fib[i - 1] + fib[i - 2]);
fibinv[i] = QP(fib[i], -1);
if (!vis[i])
prim.push_back(i), mu[i] = -1;
for (register auto j : prim)
{
if (i * j > n)
break;
vis.set(i * j);
if (i % j)
mu[i * j] = -mu[i];
else
break;
}
}
for (register int i = 1; i <= n; ++i)
for (register int j = 1; i * j <= n; ++j)
if (~mu[j])
{
if (mu[j])
F[i * j] = (LL)F[i * j] * fib[i] % mod;
}
else
F[i * j] = (LL)F[i * j] * fibinv[i] % mod;
for (register int i = 2; i <= n; ++i)
F[i] = (LL)F[i] * F[i - 1] % mod;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("SDOI2017_shuzibiaoge.in", "r", stdin);
freopen("SDOI2017_shuzibiaoge.out", "w", stdout);
#endif
Pre(maxN - 2);
T = read();
while (T--)
{
n = read(), m = read();
if (n > m)
std::swap(n, m);
register int ans = 1;
for (register int l = 1, r; l <= n; l = r + 1)
{
r = std::min(n / (n / l), m / (m / l));
ans = (LL)ans * QP( (LL)F[r] * QP(F[l - 1], -1) % mod, (LL)(n / l) * (m / l) ) % mod;
}
write(ans), putchar('\n');
}
return 0;
}

[SDOI2014] 数表

Description


$$
\sum _{i = 1} ^n \sum _{j = 1} ^m [\sigma _1 ((i, j)) \le a] \sigma _1 ((i, j)) \\
T \le 2 \times 10 ^4, 1 \le n, m \le 10 ^5, a \le 10 ^9
$$
每组数据有不同的 $a$

Solution

不妨设 $n \le m$

先考虑去掉 $\le a$ 的限制怎么做

可以知道 $\sigma _1 ((i, j)) = \sum \limits _{x | (i, j)} x$ ,于是不需要反演,可以直接这样推:
$$
\begin{aligned}
& \sum _{i = 1} ^n \sum _{j = 1} ^m \sigma _1 ((i, j)) \\
=& \sum _{i = 1} ^n \sum _{j = 1} ^m \sum _{x | (i, j)} x \\
=& \sum _{x = 1} ^n x \lfloor \frac n x \rfloor \lfloor \frac m x \rfloor
\end{aligned}
$$
然后就无路可走了

于是找另一条路走:
$$
\begin{aligned}
& \sum _{i = 1} ^n \sum _{j = 1} ^m \sigma _1 ((i, j)) \\
=& \sum _{d = 1} ^n \sigma _1 (d) \sum _{i = 1} ^n \sum _{j = 1} ^m [(i, j) = d] \\
=& \sum _{d = 1} ^n \sigma _1 (d) \sum _{x = 1} ^{\lfloor \frac n d \rfloor} \mu (x) \lfloor \frac n {dx} \rfloor \lfloor \frac m {dx} \rfloor
\end{aligned}
$$
(第二行最后那块实在是太常见了,就直接变了)

依然枚举 $T = dx$ 变为最终式:
$$
\sum _{T = 1} ^n \lfloor \frac n T \rfloor \lfloor \frac m T \rfloor \sum _{d | T} \sigma _1 (d) \mu (\frac T d)
$$
再回到题目的 $\le a$ 的限制

惊喜的发现这个式子让这个题目变得可做了

将后面这一块单独提出来看:令 $g(T) = \sum \limits _{d | T} \sigma _1 (d) \mu (\frac T d)$

我们一开始枚举的 $d$ 的意义就是 $i, j$ 的 $\gcd$ ,中间就算经过了变换,它的意义依然没有改变;也就是说,$\sigma _1 ((i, j)) \le a$ 也对应着上面 $g(T)$ 中所枚举的 $d$ 需要满足 $\sigma _1 (d) \le a$

于是我们离线将 $a$ 排序,同时将 $10 ^5$ 内的数线性筛出其约数和并按约数和排序

每次询问将满足约数和小于 $a$ 的数对其倍数算贡献,也就是动态的更新 $g(T)$ ,考虑到整除分块时需要查询前缀和,而修改只需要单点加,于是便用树状数组动态维护 $g(T)$

对 $2 ^{31} - 1$ 取模,只需要算的时候用 unsigned int ,将答案再与 $2 ^{31}$ 相与即可(注意 (1 << 31) - 1 此处会爆 int ,因为 $2 ^{31}$ 超出了 int 范围,故用 0x7FFFFFFF 为宜)

复杂度的话,视作 $n, m$ 同阶,一开始排序和线性筛即为 $\cal O(T \log T + n \log n)$ ,因为对约数和和询问排了序;处理询问时,修改处枚举倍数和树状数组有两个 $\log$ (其中有一个是 $\ln$ ,粗略算成 $\log$ 算了),回答用到整除分块和树状数组,综上,复杂度约为 $\cal O(T \sqrt n \log n + n \log ^2 n + T \log T)$

Code

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
/**********************************************************
* Author : EndSaH
* Email : hjxhb1@gmail.com
* Created Time : 2019-06-04 19:13
* FileName : SDOI2014_number.cpp
* Website : https://endsah.cf
* *******************************************************/

#include <cstdio>
#include <cctype>
#include <cmath>
#include <bitset>
#include <vector>
#include <algorithm>

typedef std::pair<int, int> pii;
typedef unsigned int uint;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define Debug(s) debug("The message in line %d, Function %s: %s\n", __LINE__, __FUNCTION__, s)
#define getchar() (ipos == iend and (iend = (ipos = _ibuf) + fread(_ibuf, 1, __bufsize, stdin), ipos == iend) ? EOF : *ipos++)
#define putchar(ch) (opos == oend ? fwrite(_obuf, 1, __bufsize, stdout), opos = _obuf : 0, *opos++ = (ch))
#define __bufsize (1 << 21 | 1)

char _ibuf[__bufsize], _obuf[__bufsize], _stk[20];
char *ipos = _ibuf, *iend = _ibuf, *opos = _obuf, *oend = _obuf + __bufsize, *stkpos = _stk;

struct END
{ ~END() { fwrite(_obuf, 1, opos - _obuf, stdout); } }
__;

inline int read()
{
register int x = 0;
register char ch;
while (!isdigit(ch = getchar()));
while (x = (x << 3) + (x << 1) + (ch & 15), isdigit(ch = getchar()));
return x;
}

template <typename _INT>
inline void write(_INT x)
{
while (*++stkpos = x % 10 ^ 48, x /= 10, x);
while (stkpos != _stk)
putchar(*stkpos--);
}

template <typename _Tp>
inline bool Chkmax(_Tp& x, const _Tp& y)
{ return x < y ? x = y, true : false; }

template <typename _Tp>
inline bool Chkmin(_Tp& x, const _Tp& y)
{ return x > y ? x = y, true : false; }

const int maxN = 1e5;
const int maxQ = 2e4;

int T;
int ans[maxN + 2], low[maxN + 2], mu[maxN + 2];
uint BIT[maxN + 2];
std::bitset<maxN + 2> vis;
std::vector<int> prim;
pii sigma[maxN + 2];

struct Ask
{
int id, n, m, a;

Ask() { }

Ask(int id, int n, int m, int a) : id(id), n(n), m(m), a(a) { }

bool operator<(const Ask& x) const
{ return a < x.a; }
} ask[maxQ + 2];

inline void Add(int x, int addval)
{
while (x <= maxN)
BIT[x] += addval, x += x & -x;
}

inline uint Query(int x)
{
register uint res = 0;
while (x)
res += BIT[x], x -= x & -x;
return res;
}

inline void Shuffle(int n)
{
prim.reserve(n / log(n));
sigma[1] = pii(1, 1), mu[1] = low[1] = 1;
for (register int i = 2; i <= n; ++i)
{
if (!vis[i])
{
prim.push_back(i);
mu[i] = -1, low[i] = i, sigma[i] = pii(i + 1, i);
}
for (register auto j : prim)
{
if (i * j > n)
break;
vis.set(i * j);
if (i % j)
low[i * j] = j, mu[i * j] = -mu[i], sigma[i * j] = pii(sigma[i].first * sigma[j].first, i * j);
else
{
low[i * j] = low[i] * j;
if (low[i] == i)
sigma[i * j] = pii(sigma[i].first + i * j, i * j);
else
sigma[i * j] = pii(sigma[i / low[i]].first * sigma[j * low[i]].first, i * j);
break;
}
}
}
std::sort(sigma + 1, sigma + n + 1);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("SDOI2014_number.in", "r", stdin);
freopen("SDOI2014_number.out", "w", stdout);
#endif
Shuffle(maxN);
T = read();
for (register int i = 1, n, m, a; i <= T; ++i)
{
n = read(), m = read(), a = read();
if (n > m)
std::swap(n, m);
ask[i] = Ask(i, n, m, a);
}
std::sort(ask + 1, ask + T + 1);
register pii* j = sigma + 1;
for (register Ask* p = ask + 1; p - ask <= T; ++p)
{
while (j - sigma <= maxN and j->first <= p->a)
{
for (register int k = 1; k * j->second <= maxN; ++k)
Add(k * j->second, j->first * mu[k]);
++j;
}
uint cans = 0;
for (register int l = 1, r; l <= p->n; l = r + 1)
{
r = std::min(p->n / (p->n / l), p->m / (p->m / l));
cans += (uint)(p->n / l) * (p->m / l) * (Query(r) - Query(l - 1));
}
ans[p->id] = cans & 0x7FFFFFFF;
}
for (register int i = 1; i <= T; ++i)
write(ans[i]), putchar('\n');
return 0;
}

To be continued