莫比乌斯反演基础
本来想写一篇数论基础的，后来发现太长了省选之前填不完就弃了
所以现在是莫比乌斯反演基础。
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;
}
2022年8月04日 01:50
National Stock Exchange has got some specific timing, during which the trading will be scheduled and later there will not be an official trading session processed. There will be no trading possessed during the Saturday and Sunday along with some National Holidays declared by the Indian Government, and if anyone is trading, then they must be aware of these NSE holiday list. Stock market holidays National Stock Exchange is open from Monday to Friday during the business hours to operate share market trading. There will be no trading possessed during the Saturday and Sunday along with some National Holidays declared by the Indian Government, and if anyone is trading, then they must be aware of these NSE holiday list.