莫比乌斯反演基础
本来想写一篇数论基础的，后来发现太长了省选之前填不完就弃了
所以现在是莫比乌斯反演基础。
1 定义
$F(n) = \sum_{d|n}f(d)$可以反演至$f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)$或$f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d})$。
可以理解为，前后等价。
$\mu(i)$为莫比乌斯函数。
1. 如果$i=1$，则$\mu(i)=1$
2. 如果$i=p_1p_2p_3...p_k$, $\{p_k\}$各不相同的素数，那么$\mu(i)=(-1)^k$
3. 否则$\mu(i)=0$
P.S 以下预备知识需要你熟练掌握：线性筛，数学推导。
2 例题
2.1 BZOJ 2301 Problem B
$n$次询问，每次询问多少个$(x,y)$满足，$a\leq x\leq b, c\leq y\leq d$，且$(x,y)=k$。
$1 \leq n, a, b, c, d \leq 5\times 10^4$
【题解】
首先询问拆分。
也就是现在要求求出多少个$(x,y)$满足$1\leq x\leq n, 1\leq y \leq m$，且$(x,y)=k$。
接下来就是莫比乌斯反演的事情啦！
那我们令$f(i)$为$1 \leq x \leq n, 1 \leq y \leq m$且$(x,y)=i$的数对$(x,y)$的个数。
令$F(i)$为为$1 \leq x \leq n, 1 \leq y \leq m$且$i|(x,y)$的数对$(x,y)$的个数。
那么就可以反演啦！
显然可以得到$F(i)=\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor$
反演可得
$f(i) = \sum_{i|d}\mu(\frac{d}{i})F(d)$
$f(i) = \sum_{i|d}\mu(\frac{d}{i})\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$
显然原题要求$f(k)$，那么枚举$k$的每一个倍数$d$即可。
但是这样的复杂度是$O(n)$的，考虑如何优化。
观察发现，$\lfloor \frac{n}{d}\rfloor$最多有$2\sqrt{n}$个取值。
为什么呢？
分析$\lfloor \frac{n}{d} \rfloor (1 \leq d \leq n)$的取值：
1. 当$1\leq d\leq \lfloor \sqrt{n} \rfloor$时，$\lfloor \frac{n}{d} \rfloor$最多有$\sqrt{n}$种不同取值。
2. 当$\lfloor \sqrt{n} \rfloor +1 \leq d \leq n$时，由于$\lfloor \frac{n}{d} \rfloor \leq \lfloor \sqrt{n} \rfloor$，所以也最多有$\sqrt{n}$种不同取值。
综上，最多共有$2\sqrt{n}$个取值。
同样的，$\lfloor \frac{m}{d}\rfloor$最多有$2\sqrt{m}$个取值。
那么问题来啦！
$\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$有多少个取值呢？
啥？你说有$4\sqrt{nm}$个？Naive！
所以我们枚举这$2(\sqrt{n}+\sqrt{m})$个取值，对莫比乌斯函数维护前缀和，就能在$O(\sqrt{n})$内解答了。
那么，如何枚举除法呢？
if(n>m) swap(n, m);
for (int i=1, last; i<=n; i=last+1) {
last = min(n/(n/i), m/(m/i));
ret += (n/i)*(m/i)*(sum[last]-sum[i-1]);
}
return ret;
是不是很简单啦？
那么代码实现也就水到渠成了。
# include <stdio.h>
# include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int M = 500010;
int q, a, b, c, d, k;
int p[M], pn=0;
int mu[M], s[M];
bool wait[M];
inline ll solve(int n, int m) {
ll res = 0;
if(n>m) swap(n, m);
for (int i=1, last=0; i<=n; i=last+1) {
last = min(n/(n/i), m/(m/i));
res += (ll)(s[last] - s[i-1]) * (n/i) * (m/i);
}
return res;
}
int main() {
scanf("%d", &q);
mu[1] = 1;
for (int i=2; i<=500000; ++i) {
if(!wait[i]) {
p[++pn] = i;
mu[i] = -1;
}
for (int j=1; j<=pn&&i*p[j]<=500000; ++j) {
wait[i*p[j]] = 1;
if(i%p[j]==0) {
mu[i*p[j]] = 0;
break;
} else mu[i*p[j]] = -mu[i];
}
}
for (int i=1; i<=500000; ++i)
s[i] = s[i-1] + mu[i];
while(q--) {
scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
long long ans = solve(b/k, d/k) - solve((a-1)/k, d/k) - solve(b/k, (c-1)/k) + solve((a-1)/k, (c-1)/k);
printf("%lld\n", ans);
}
return 0;
}
2.2 BZOJ2820 YY的GCD
求有多少个数对$(x,y)$满足$1\leq x\leq n, 1\leq y\leq m$且$(x,y)$是质数。
$n \leq 10^7, T\leq 10^4$
【题解】
设$(x,y)=p$，那么问题转化为对于每个**质数**$p$，求出有多少个数对$(x,y)$满足$1 \leq x \leq \lfloor \frac{n}{p} \rfloor, 1 \leq y \leq \lfloor \frac{m}{p} \rfloor$，且$(x,y)=1$。
那么答案就是
$ans=\sum_p^{min(n,m)} \sum_{d=1}^{min(n,m)} \mu(d) \lfloor \frac{n}{pd} \rfloor \lfloor \frac{m}{pd} \rfloor$
令$pd=T$，则
$ans = \sum_T^{min(n,m)} \sum_{p|T} \mu(\frac{T}{p}) \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T} \rfloor$
定值可以提取，则
$ans = \sum_T^{min(n,m)} \lfloor \frac{n}{T} \rfloor \lfloor \frac{m}{T}\rfloor \sum_{p|T} \mu(\frac{T}{p})$
所以暴力枚举每个质数，更新倍数，处理前缀和即可。复杂度$O(n)$。
总复杂度$O(n)$。
需要较强的公式推导和代换能力。
# include <stdio.h>
# include <algorithm>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 10000010;
const int P = 4000010;
bool wait[M];
int p[P], pn=0;
int mu[M], n, m;
ll s[M];
inline ll solve(int n, int m) {
ll res=0;
if(n>m) swap(n, m);
for (int i=1, last=0; i<=n; i=last+1) {
last=min(n/(n/i), m/(m/i));
res=res+(ll)(n/i)*(m/i)*(s[last]-s[i-1]);
}
return res;
}
int main() {
mu[1] = 1;
for (int i=2; i<=10000000; ++i) {
if(!wait[i]) {
p[++pn] = i;
mu[i] = -1;
}
for (int j=1; j<=pn&&i*p[j]<=10000000; ++j) {
wait[i*p[j]] = 1;
if(i%p[j]==0) {
mu[i*p[j]] = 0;
break;
} else mu[i*p[j]] = -mu[i];
}
}
for (int i=1; i<=pn; ++i)
for (int j=1; j*p[i]<=10000000; j++) s[j*p[i]] += mu[j];
for (int i=1; i<=10000000; ++i) s[i] += s[i-1];
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
printf("%lld\n", solve(n, m));
}
return 0;
}
2.3 BZOJ 3529 数表
令$F(i)$为$i$的约数和，$q$次给定$n,m,a$，求$\sum_{1\leq i\leq n, 1\leq j\leq m, F(gcd(i,j)) \leq a} F(gcd(i,j))~mod~ 2^{31}$
$n, m \leq 10^5, q \leq 20000, a \leq 10^9$
【题解】
假定没有$a$的限制，只是求$1 \leq x \leq n, 1 \leq y \leq m, (x,y)=i$的对数，那么：
$f(i) = \sum_{i|d}\mu(\frac{d}{i})\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$
$F(i)$可以利用线性筛处理出来。
考虑答案怎么表示：
$ans = \sum_{i=1}^{min(n,m)} F(i) \sum_{i|d} \mu(\frac{d}{i})\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$
把$\sum$换位，
$ans = \sum_{d=1}^{min(n,m)} \lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor \sum_{i|d}F(i)\mu(\frac{d}{i})$
对比上一题，同理暴力枚举每个质数，更新倍数，处理前缀和即可。
那么考虑了$a$的限制了呢？
离线，对$a$排序，按照$F(i)$将$i$排序，发现从小到大每次只要维护前缀和的增加即可，用树状数组。
$O(nlog^2n + q\sqrt{n}logn)$
# include <stdio.h>
# include <string.h>
# include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int M = 500010, Ms = 200000;
bool wait[M];
int p[M], pn=0, mu[M];
struct Fs {
int s, id;
inline void init(int x) {
s = 0; id = x;
}
friend bool operator <(Fs a, Fs b) {
return a.s<b.s || (a.s==b.s && a.id<b.id);
}
}F[M];
int Q;
struct ques {
int n, m, a, id;
friend bool operator <(ques a, ques b) {
return a.a<b.a;
}
}q[M];
int ans[M];
struct BIT {
int c[M], n;
inline void init(int x) {
n = x;
memset(c, 0, sizeof(c));
}
inline int lb(int x) {return x&(-x);}
inline void change(int x, int del) {
for (; x<=n; x+=lb(x)) c[x]+=del;
}
inline int ask(int x) {
int ret=0;
for (; x; x-=lb(x)) ret+=c[x];
return ret;
}
}T;
inline int solve(int n, int m) {
if(n>m) swap(n, m);
int ret=0;
for (int i=1, last=0; i<=n; i=last+1) {
last = min(n/(n/i), m/(m/i));
ret += (n/i)*(m/i)*(T.ask(last)-T.ask(i-1));
}
return ret;
}
int main() {
mu[1] = 1;
for (int i=2; i<=Ms; ++i) {
if(!wait[i]) {
p[++pn] = i;
mu[i] = -1;
}
for (int j=1; j<=pn&&i*p[j]<=Ms; ++j) {
wait[i*p[j]] = 1;
if(i%p[j]==0) {
mu[i*p[j]]=0;
break;
}
mu[i*p[j]] = -mu[i];
}
}
for (int i=1; i<=Ms; ++i)
F[i].init(i);
for (int i=1; i<=Ms; ++i)
for (int j=i; j<=Ms; j+=i)
F[j].s += i;
sort(F+1, F+Ms+1);
scanf("%d", &Q);
for (int i=1; i<=Q; ++i) {
scanf("%d%d%d", &q[i].n, &q[i].m, &q[i].a);
q[i].id=i;
}
sort(q+1, q+Q+1);
T.init(Ms);
int cur = 0;
for (int i=1; i<=Q; ++i) {
while(cur+1 <= Ms && F[cur+1].s<=q[i].a) {
++cur;
for (int j=1; j*F[cur].id<=Ms; ++j)
T.change(j*F[cur].id, F[cur].s*mu[j]);
}
ans[q[i].id] = solve(q[i].n, q[i].m);
}
for (int i=1; i<=Q; ++i) printf("%d\n", ans[i]&0x7fffffff);
return 0;
}
2.4 BZOJ2154 Crash的数字表格 (BZOJ2693 jzptab)
给$n,m$，求$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$。
$1 \leq n, m \leq 10^7$
【题解】
$ans = \sum_{i=1}^{n}\sum_{j=1}^{m} \frac{ij}{(i,j)}$
枚举$(i,j)=d$。
令$F(x,y) = \sum_{1\leq i \leq x, 1\leq j \leq y}^{(i,j)=1}ij$
那么$ans = \sum_{d=1}^{min(n,m)}\frac{d^2F(\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor)}{d} = \sum_{d=1}^{min(n,m)}dF(\lfloor \frac{n}{d} \rfloor \lfloor \frac{m}{d} \rfloor)$
$S(x,y) = \sum_{i=1}^{x} \sum_{j=1}^{y} ij = \frac{xy(x+1)(y+1)}{4}$
$F(x,y) = \sum_{i=1}^{min(x,y)}\mu(i)\times i^2\times S(\lfloor \frac{x}{i} \rfloor, \lfloor \frac{y}{i}\rfloor)$
对两个式子进行计算，复杂度分别为$O(\sqrt{n})$和$O(\sqrt{n})$。乘起来就是$O(n)$。
进一步，如果有多组询问呢？
$ans = \sum_{d=1}^{min(n,m)}d \sum_{i=1}^{min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)}\mu(i)\times i^2\times S(\lfloor \frac{x}{di} \rfloor, \lfloor \frac{y}{di}\rfloor)$
令$T = di$
那么$ans = \sum_{d=1}^{min(n,m)}d \sum_{i=1}^{min(\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor)}\mu(i)\times i^2\times S(\lfloor \frac{x}{di} \rfloor, \lfloor \frac{y}{di}\rfloor)$
$ans = \sum_{D=1}^{min(n,m)}\sum_{i|D}\frac{D}{i}\times\mu(i)\times i^2 \times S(\lfloor\frac{x}{D}\rfloor\lfloor\frac{y}{D}\rfloor)$
发现后面那一坨跟$i$无关，提前。
$ans = \sum_{D=1}^{min(n,m)}S(\lfloor\frac{x}{D}\rfloor\lfloor\frac{y}{D}\rfloor)\sum_{i|D}\frac{D}{i}\times\mu(i)\times i^2$
$ans = \sum_{D=1}^{min(n,m)}S(\lfloor\frac{x}{D}\rfloor\lfloor\frac{y}{D}\rfloor)\sum_{i|D}D\times\mu(i)\times i$。
令$g(D)=\sum_{i|D}D\times\mu(i)\times i$。
则$g(D)=D\sum_{i|D}i\times \mu_i$。
对于后面维护前缀和即可。
如果$D$是质数，那么$g(D)=D\times (1\times 1 + D \times (-1)) = -D^2+D$。
如果我们已经知道了$g(D')$，$g(D=D' \times p)$怎么求呢？
首先很好证明$g(D)$是积性函数，那么如果$(D', p)=1$，则$g(D)=g(D')\times g(p)$。
如果$(D', p) = 0$，那么根据线性筛的性质，$g(D)=g(D')\times p$。
那么就能线性筛啦！
预处理$O(n)$，单次询问$O(\sqrt{n})$。
# include <stdio.h>
# include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int M = 10000000, mod = 20101009, P = 4000010;
bool wait[M+10];
int p[P], pn=0, n, m;
int g[M+10];
inline int S(int x, int y) {
return 1ll * (1ll*x*(x+1)/2%mod) * (1ll*y*(y+1)/2%mod) % mod;
}
int main() {
g[0] = 0, g[1] = 1;
for (int i=2; i<=M; ++i) {
if(!wait[i]) {
p[++pn] = i;
g[i] = 1ll * i * (1-i+mod) % mod;
}
for (int j=1; j<=pn && i*p[j] <= M; ++j) {
wait[i*p[j]] = 1;
if(i%p[j] == 0) {
g[i*p[j]] = 1ll * g[i] * p[j] % mod;
break;
} else g[i*p[j]] = 1ll * g[i] * g[p[j]] % mod;
}
}
for (int i=1; i<=M; ++i) g[i] = (g[i-1] + g[i]) % mod;
scanf("%d%d", &n, &m);
int ans = 0;
if(n>m) swap(n, m);
for (int i=1, last=0; i<=n; i=last+1) {
last = min(n/(n/i), m/(m/i));
ans = ans + 1ll * S(n/i, m/i) * (g[last] - g[i-1] + mod) % mod;
ans %= mod;
}
printf("%d\n", ans);
return 0;
}
# include <stdio.h>
# include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int M = 10000000, mod = 100000009, P = 4000010;
bool wait[M+10];
int p[P], pn=0, n, m;
int g[M+10];
inline int S(int x, int y) {
return 1ll * (1ll*x*(x+1)/2%mod) * (1ll*y*(y+1)/2%mod) % mod;
}
int main() {
g[0] = 0, g[1] = 1;
for (int i=2; i<=M; ++i) {
if(!wait[i]) {
p[++pn] = i;
g[i] = 1ll * i * (1-i+mod) % mod;
}
for (int j=1; j<=pn && i*p[j] <= M; ++j) {
wait[i*p[j]] = 1;
if(i%p[j] == 0) {
g[i*p[j]] = 1ll * g[i] * p[j] % mod;
break;
} else g[i*p[j]] = 1ll * g[i] * g[p[j]] % mod;
}
}
for (int i=1; i<=M; ++i) g[i] = (g[i-1] + g[i]) % mod;
int T; scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
int ans = 0;
if(n>m) swap(n, m);
for (int i=1, last=0; i<=n; i=last+1) {
last = min(n/(n/i), m/(m/i));
ans = ans + 1ll * S(n/i, m/i) * (g[last] - g[i-1] + mod) % mod;
ans %= mod;
}
printf("%d\n", ans);
}
return 0;
}
评论 (0)
