莫比乌斯反演
没想到吧，真的有莫比乌斯反演专题！我现在已经看不懂我当时在写什么了！
莫比乌斯函数
1. 定义
由唯一分解定理，可以将正整数n写成n=∏ki=1paii=pa11pa22..pakk的形式，莫比乌斯函数μ(n)的定义为
2. 性质
性质1
证明：设d为n的约数，则d=∏ki=1pbii，其中0≤bi≤ai。
对于μ(d)，如果∃bi≥2，则μ(d)=0。因此，有贡献的μ(d)一定为Cik×(−1)i，也就是每个质数最多取一次。
则∑d|nμ(d)=k∑i=0Cik×(−1)i，又(a−b)k=k∑i=0Cikakbk−i
(1−1)k=k∑i=0Cik×(−1)k，故∑d|nμ(d)=0k=0
3. 与其他数论函数的关系
(1) μ∗I=e
证明：设n=∏ki=1paii,n′=∏ki=1pi
则(μ∗I)(n)=∑d|nμ(d)=∑d|n′μ(d)=k∑i=0(−1)i
呃，等等，好像性质一已经证明过了啊。(μ∗I)(n)=[n=1]=e，
因此，μ是I的狄利克雷逆。
(2) μ∗id=φ
这个在基础篇的性质证明过了QWQ，不写辣
(3) μ∗d=I
证明：(I∗I)(n)=∑d|nI(d)=∑d|n1=d(n)
∴d=I∗I，又μ=I−1
∴μ∗d=I
4. 线性筛法求莫比乌斯函数
void Mobius(int n){
mu[1] = 1;
for (int i=2;i<=n;++i){
if (!st[i]) p[++cnt] = i, mu[i] = -1;
for (int j=1;p[j]<=n/i;++j){
st[p[j] * i] = true;
if (i % p[j] == 0) break;
mu[p[j] * i] = -mu[i];
}
}
}
// 当i为质数时, 显然mu[i]=-1
// 当p[j]为i的最小质数时, 就说明p[j]这个质数出现了>1次, 因此mu[i * p[j]] = 0
// 否则
// (1) mu[i]=0, mu[p[j] * i] = 0
// (2) mu[i]不为0, p[j] * i就相当于增加了一个质数, 因此mu[p[j] * i] = -mu[i]
莫比乌斯反演
莫反的函数定义和转换过程大多依靠平时积累，见过类似套路，就会，没见过，就寄。
1. 定义
设f(n)为数论函数(定义在正整数集合上的函数)
因数形式：
- F(n)=f∗I=∑d|nf(d)⇔f(n)=∑d|nμ(d)×F(nd)，
证明（利用狄利克雷卷积）：因为F(n)=f∗I，则f=F∗I−1=F∗μ
即f(n)=∑d|nμ(d)×F(nd)。
证明（利用性质1+二重积分交换次序的思想）：
∑d|nμ(d)×F(nd)=∑d|nμ(d)×∑i|ndf(i)=∑i|nf(i)∑d|niμ(d)
（i能取到所有d可以取到的取值，这样反过来看，把i提到前面）
又当且仅当n=i时，∑d|niμ(d)=1，因此∑d|nμ(d)×F(nd)=f(n)
倍数形式：
- F(n)=∑n|Nf(N)⇔f(n)=∑n|NF(N)μ(Nn)，（枚举N为n的所有倍数，N∈[n,+∞)）
证明：∑n|NF(N)μ(Nn)=∑n|Nμ(Nn)∑N|if(i)
设d=Nn，则N=dn，则dn|i，即d|in
因此∑n|Nμ(Nn)∑N|if(i)=∑d|inμ(d)∑N|if(i)
又当且仅当n=i时，∑d|niμ(d)=1，因此f(n)=∑n|NF(N)μ(Nn)
运用莫反的时候，通常都是因为F(n)好求，但是f(n)不好求，因此将f(n)用F,μ表示出来。
2. 应用1：莫反+整数分块
p2522 Problem b
数据范围：1≤n,k≤5×104;1≤a≤b≤5×104;1≤c≤d≤5×104
思路：详细的整理一下吧。
首先，题目要我们求的东西，可以先拆成一个二维前缀和，A[a,b][c,d]=A[1,b][1,d]−A[1,b][1,c−1]−A[1,a−1][1,d]+A[1,a−1][1,c−1]。
设f(k)=a∑x=1b∑y=1[(x,y)=k]，然后我们方便求的是这个F(k)=a∑x=1b∑y=1[k|(x,y)]，且F(k)=∑k|Nf(N)
则代入莫反倍数形式得f(k)=∑k|Nμ(Nk)F(N)
先求F(N)。首先，N|(x,y)，也就是说，N|x,N|y，因此所有满足条件的点对数量为⌊aN⌋×⌊bN⌋
则f(k)=∑k|Nμ(Nk)⌊ak⌋×⌊bk⌋，设$t=\frac N k ，显然枚举t$的结果为1,2,..,这样的整数，N=tk。
f(k)=∑tμ(t)⌊atk⌋×⌊btk⌋，再运用整数分块的知识进行求解即可，注释都写在代码里吧。
#include pll;
#define xx first
#define yy second
#define ls (oo << 1)
#define rs (oo << 1 | 1)
#define PI acos(-1.0)
ll read(void);
int n, cnt;
const int N = 5e4 + 5;
int p[N], mu[N];
int pre[N];
bool st[N];
//求Mobius函数和前缀和(分块的时候用)
void Mobius(int n){
mu[1] = 1;
for (int i=2;i<=n;++i){
if (!st[i]) p[++cnt] = i, mu[i] = -1;
for (int j=1;p[j]<=n/i;++j){
st[p[j] * i] = true;
if (i % p[j] == 0) break;
mu[p[j] * i] = -mu[i];
}
}
for (int i=1;i<=n;++i){
pre[i] = pre[i - 1] + mu[i];
}
}
ll f(int a, int b, int k){
a /= k, b /= k;
ll res = 0, n = min(a, b), l = 1, r;
// 在[l,r]这段,(a/l)*(b/l)为定值,那么展开和式, 可以打包计算这一部分的和为(定值*mu的前缀和)
while (l <= n){
r = min(n, min(a / (a / l), b / (b / l)));
res += 1LL * (pre[r] - pre[l - 1]) * (a / l) * (b / l);
l = r + 1;
}
return res;
}
void solve(){
int a, b, c, d, k;
a = read(), b = read(), c = read(), d = read(), k = read();
// 二维前缀和,或者说一个简单的容斥
ll res = f(b, d, k) - f(b, c - 1, k) - f(a - 1, d, k) + f(a - 1, c - 1, k);
printf("%lld\n", res);
}
int main(void){
int T;
Mobius(N - 1);
T = read();
while (T--){
solve();
}
return 0;
}
ll read(void){
ll x = 0, f=1;char ch;
do{ch = getchar();if (ch == '-') f=-1;}while(ch<'0' || ch>'9');
do{x = x*10 + (ch-'0');ch = getchar();}while(ch>='0' && ch<='9');
return x*f;
}
/*
敬告kz:
====================================
1. 相信自己
2. 看清题意, 考虑清楚再动手
3. **** 今天的数组有没有开小呀 ？ **** **** 今天的数组有没有开小呀 ？ ****
4. 是不是想复杂了？
5. 数据溢出？
6. 数组越界？边界情况？
6. 不要犯低级错误！！！ 时间复杂度？空间复杂度？精度有没有问题？
====================================
* 提交的时候注意看编译器！c++17 / c++20 / python3
*/
3. 应用2：莫反+提取公因数
p3327约数个数和 莫反+双分块
设d(x)为x的约数个数，给定T组n,m，求N∑i=1M∑j=1d(i×j)
数据范围：1≤N,M,T≤5×104
N∑i=1M∑j=1d(i×j)=N∑i=1M∑j=1∑x|i∑y|j[(x,y)=1]
证明：设i=∏ki=1paii,j=∏ki=1pbii，0≤ai,bi
则i×j=∏ki=1pai+bii，d(i×j)=∏ki=1(ai+bi+1)
即从i中选出约数x，j中选出约数y，对于p1而言，若要求(x,y)=1
则可以x=1,y=1，或者x=1,y=∈[p1,pb11]，或者x∈[p1,pa11],y=1
一共是(a1+b1+1)种取法，其他质数同理。根据乘法原理，这些取法正好就是d(i×j)。
- 设出f(n),F(n)。
设f(n)=N∑i=1M∑j=1∑x|i∑y|j[(x,y)=n]，显然f(1)就是答案。
设F(n)=N∑i=1M∑j=1∑x|i∑y|j[n|(x,y)]，则F(n)=∑n|df(d)
即f(n)=∑n|dμ(dn)F(d)令T=min，则f(1)=\sum\limits _{d=1}^T\mu(d)F(d)。
- 再化简F。
F(n)=\sum\limits _{i=1}^N \sum\limits_{j=1}^M \sum\limits _{x|i} \sum\limits_{y|j} [n|(x,y)]=\sum\limits _{x=1}^N \sum\limits_{y=1}^M \lfloor \frac N x \rfloor \lfloor \frac M y \rfloor [n|(x,y)]
证明：首先，x|i,y|j，那么x,y肯定是能取到[1,N],[1,M]的。当x,y固定后，[n|(x,y)]和i,j是没有关系的，我们可以把它提出来。那么，里面就变成了\sum\limits _{i=1}^{\lfloor \frac N x \rfloor}\sum\limits _{j=1}^{\lfloor \frac M y \rfloor}1，也就是N,M里面有多少个i,j，它们是x,y的倍数，得证。
下面再消掉[n|(x,y)]这个条件。
设x'=\lfloor \frac x n \rfloor,y'=\lfloor \frac y n \rfloor
F(n)=\sum\limits _{x=1}^N \sum\limits_{y=1}^M \lfloor \frac N x \rfloor \lfloor \frac M y \rfloor [n|(x,y)]=\sum\limits _{x'=1}^{\lfloor \frac N n \rfloor}\sum\limits _{y'=1}^{\lfloor \frac M n \rfloor}\lfloor \frac N {nx'} \rfloor\lfloor \frac M {ny'} \rfloor
令N'=\lfloor \frac N n \rfloor,M'=\lfloor \frac M n \rfloor
F(n)=\sum\limits _{x'=1}^{N'} \sum\limits_{y'=1}^{M'} \lfloor \frac {N'} {x'} \rfloor \lfloor \frac {M'} {y'} \rfloor=(\sum\limits _{x'=1}^{N'} \lfloor \frac {N'} {x'} \rfloor)\times(\sum\limits_{y'=1}^{M'} \lfloor \frac {M'} {y'} \rfloor)
令h(n)=\sum\limits_{i=1}^{n} \lfloor \frac {n} {i} \rfloor)，也就是标准整数分块，则F(n)=h(N')\times h(M')。
- 再求f(1)
f(1)=\sum\limits _{d=1}^T\mu(d)h(\lfloor \frac N d \rfloor)h(\lfloor \frac M d \rfloor)
由于h(x)只和x有关，所以可以再分一次块，因此每次查询复杂度O(\sqrt N)，总时间复杂度O(N\sqrt N)。
int cnt;
const int N = 5e4 + 5;
int p[N], h[N], pre[N], mu[N];
bool st[N];
void Mobius(int n){
mu[1] = 1;
for (int i=2;i<=n;++i){
if (!st[i]) p[++cnt] = i, mu[i] = -1;
for (int j=1;p[j]<=n/i;++j){
st[p[j] * i] = true;
if (i % p[j] == 0) break;
mu[p[j] * i] = -mu[i];
}
}
for (int i=1;i<=n;++i){
pre[i] = pre[i - 1] + mu[i];
}
}
void H(int n){
for (int i=1;i<=n;++i){
for (int l=1, r;l<=i;l=r + 1){
r = min(i, i / (i / l));
h[i] += (r - l + 1) * (i / l);
}
}
}
void solve(){
int n, m;
n = read(), m = read();
ll res = 0;
int k = min(n, m);
for (int l=1, r;l<=k;l=r + 1){
r = min(k, min(n / (n / l), m / (m / l)));
res += (ll)(pre[r] - pre[l - 1]) * h[n / l] * h[m / l];
}
printf("%lld\n", res);
}
int main(void){
int T;
Mobius(N - 1);
H(N - 1);
T = read();
while (T--){
solve();
}
return 0;
}