讲道理莫比乌斯反演也算组合数学，不过因为听起来很高大上所以新开了一篇。
抄袭来源
https://www.cnblogs.com/peng-ym/p/8647856.html
https://www.cnblogs.com/peng-ym/p/9446555.html
https://www.luogu.org/blog/An-Amazing-Blog/mu-bi-wu-si-fan-yan-ji-ge-ji-miao-di-dong-xi
#define
$[A]$：若事件$A$成立为$1$，反之为$0$。
$\dfrac{n}{i}$：默认向下取整。有的懒得打向下取整号了
凡出现$n$和$m$，默认$n<m$。
整除分块
在$O(\sqrt{n})$时间内求出$\sum\limits_{i=1}^n\left\lfloor\dfrac{n}{i}\right\rfloor$。
显然$\left\lfloor\dfrac{n}{i}\right\rfloor$只有$O(\sqrt{n})$种取值。
然后有个性质就是对于$\forall i\in[l,(n/(n/l))]$，都有$\left\lfloor\dfrac{n}{i}\right\rfloor=\left\lfloor\dfrac{n}{l}\right\rfloor$。
这样就能把$n$分成$\sqrt{n}$段，每段统一求和。
int sum(int n){
int ans=0;
for(register int l=1,r;l<=n;l=r+1){
r=n/(n/l);
ans+=(r-l+1)*(n/l);
}
return ans;
}
同理也能做到$O(\sqrt{n})$求$\sum\limits_{i=1}^n\left\lfloor\dfrac{n}{i}\right\rfloor\left\lfloor\dfrac{m}{i}\right\rfloor$，也能把r-l+1换成别的，甚至可以用于求$\sum\limits_{i=1}^nf(\lfloor\dfrac{n}{i}\rfloor,\lfloor\dfrac{m}{i}\rfloor)$。
证明的话「算法竞赛·进阶指南」关于「余数求和」一题的解法写的就很好。
莫比乌斯函数
定义
定义$\mu(n)$为莫比乌斯函数。
根据算数基本定理将$n$分解：$n=\prod\limits_{i=1}^kp_i^{c_i}$
如果$\exists c_i>1$，则$\mu(n)=0$。
否则$\mu(n)=(-1)^k$。
特别的，$\mu(1)=1$。
性质
1.$\mu(n)$为积性函数
于是就能线筛它：
int prime[maxn],mu[maxn],cnt,n;
bool is[maxn];
void sieve(){
mu[1]=is[1]=1;
for(register int i=2;i<=n;++i){
if(!is[i])prime[++cnt]=i,mu[i]=-1;
for(register int j=1;j<=cnt&&i*prime[j]<=n;++j){
is[i*prime[j]]=1;
if(i%prime[j]==0){mu[i*prime[j]]=0;break;}
mu[i*prime[j]]=-mu[i];
}
}
}
2.$\sum\limits_{d|n}\mu(d)=[n=1]$
肥肠重要的性质。
证明：
$n=1$时为$1$。
$n>1$时，将$n$分解为$\prod\limits_{i=1}^kp_i^{c_i}$。
考虑它每个约数的贡献，若$c_i>1$则贡献为零，我们只考虑$c_i\le 1$的情况，也就相当于选出若干个$p_i$。
选$i$个$p_i$有$C_k^i$种情况，贡献和为：
$\sum\limits_{i=0}^kC_k^i(-1)^i$
后面乘上个$1^{k-i}$：
$=\sum\limits_{i=0}^kC_k^i(-1)^i1^{k-i}$
这不二项式定理吗？
$=(-1+1)^k$
$=0$
3.$\sum\limits_{d|n}\dfrac{\mu(d)}{d}=\dfrac{\varphi(n)}{n}$
狄雷克雷卷积中会证明。
狄雷克雷卷积
杜教筛里会用到，这里也用来证明莫比乌斯反演。
常见积性函数
欧拉函数$\varphi(n)$，约数个数函数$d(n)$，约数和函数$\sigma(n)$，莫比乌斯函数$\mu(n)$
下面是一些刚见到的完全积性函数：
- 元函数$e(n)=[n=1]$
- 常函数$1(n)=1$
- 单位函数$id(n)=n$
- 幂函数$id^k(n)=n^k$
定义
卷积的符号为$*$。
对于函数$f(n)$和$g(n)$，定义：
$(f*g)(n)=\sum\limits_{d|n}f(d)g(\dfrac{n}{d})$
写的时候可以把$(n)$省略掉。
性质
1.交换律
$f*g=g*f$
2.结合律
$(f*g)*h=f*(g*h)$
3.分配律
$(f+g)*h=f*h+g*h$
4.积性函数卷积性函数还是积性函数
5.$e(n)$就是卷积里的单位元，即$f*e=f$
下面$2$条是由$\mu,\varphi$自身的性质得来的：
6.$\mu*1=e$
7.$\varphi*1=id$
我们来用这$2$条性质证明$\sum\limits_{d|n}\dfrac{\mu(d)}{d}=\dfrac{\varphi(n)}{n}$：
给$\mu$卷个$id$：
$\mu*id=\mu*\varphi*1$
$\mu*id=\varphi*e$
$\sum\limits_{d|n}\mu(d)\dfrac{n}{d}=\varphi(n)$
$\sum\limits_{d|n}\dfrac{\mu(d)}{d}=\dfrac{\varphi(n)}{n}$
莫比乌斯反演
式子
就是这个：
$f(n)=\sum\limits_{d|n}g(d)\leftrightarrow g(n)=\sum\limits_{d|n}\mu(d)f(\dfrac{n}{d})$
还有一种形式：
$f(d)=\sum\limits_{d|n}g(n)\leftrightarrow g(d)=\sum\limits_{d|n}\mu(\dfrac{n}{d})f(n)$
证明
$f(n)=\sum\limits_{d|n}g(d)$
可以看做$f=g*1$
两边都卷个$\mu$：
$f*\mu=g*1*\mu$
前面写过$\mu*1=e,f*e=f$
则$f*\mu=g$
即$g(n)=\sum\limits_{d|n}f(d)\mu(\dfrac{n}{d})$
栗子
莫比乌斯反演能干啥？
举个栗子：求$\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=k]$
正规做法
设$f(d)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=d],g(d)=\sum\limits_{d|n}f(n)$
可以发现$g(d)$就是在枚举$d|gcd(i,j)$的倍数的情况，即前$n$个数中能被$d$整除的数的个数和前$m$个数中能被$d$整除的数的个数。
则$g(d)=\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor$。
显然可以莫比乌斯反演，$f(i)=\sum\limits_{i|d}\mu(\dfrac{d}{i})g(d)=\sum\limits_{i|d}\mu(\dfrac{d}{i})\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor$。
答案为$f(k)=\sum\limits_{k|d}\mu(\dfrac{d}{k})\left\lfloor\dfrac{n}{d}\right\rfloor\left\lfloor\dfrac{m}{d}\right\rfloor$，枚举$k$的倍数，上界显然为$\left\lfloor\dfrac{n}{k}\right\rfloor$：
$f(k)=\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\mu(i)\left\lfloor\dfrac{n}{ik}\right\rfloor\left\lfloor\dfrac{m}{ik}\right\rfloor$
把$n,m$都除以$k$，预处理$\mu$的前缀和，后面这一坨就能整除分块$O(\sqrt{n})$做了。
常见做法
真的做反演题的时候用得最多的还是$\sum\limits_{d|n}\mu(d)=[n=1]$。
还是这道题，枚举$k$的倍数：
$\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=k]$
$=\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}[gcd(i,j)=1]$
直接把$\mu$的性质往上套：
$=\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum\limits_{d|gcd(i,j)}\mu(d)$
$d|gcd(i,j)$和$d|i,d|j$是等价的，然后我们改为枚举$d$，上界为$\left\lfloor\dfrac{n}{k}\right\rfloor$，再变换一下求和顺序：
$=\sum\limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}[d|i]\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}[d|j]\mu(d)$
显然，$\sum\limits_{i=1}^n[d|i]=\left\lfloor\dfrac{n}{d}\right\rfloor$：
$=\sum\limits_{d=1}^{\lfloor\frac{n}{k}\rfloor}\mu(d)\left\lfloor\dfrac{n}{dk}\right\rfloor\left\lfloor\dfrac{m}{dk}\right\rfloor$
杜教筛
做反演题的时候有些是需要杜教筛的，然后就被送过来学了。
杜教筛可以在$O(n^{\frac{2}{3}})$求出某些数论函数的单项前缀和。
推导
假设我们有函数$f$，前缀和记为$S$，求$S(n)$。
设出另外两个函数$g,h$，满足$h=f*g$。
即$h=\sum\limits_{d|n}g(d)f(\dfrac{n}{d})$
对$h$做个前缀和：
$\sum\limits_{i=1}^nh(i)=\sum\limits_{i=1}^n\sum\limits_{d|i}g(d)f(\dfrac{i}{d})$
我们发现等号后面两个$\sum$就是把$1\sim n$的约数枚举了一遍。
于是改为枚举$d$：
$\sum\limits_{i=1}^nh(i)=\sum\limits_{d=1}^ng(d)\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(\dfrac{id}{d})=\sum\limits_{d=1}^ng(d)S(\dfrac{n}{d})$
把$d=1$提出来：
$\sum\limits_{i=1}^nh(i)=g(1)S(n)+\sum\limits_{d=2}^ng(d)S(\dfrac{n}{d})$
移项：
$g(1)S(n)=\sum\limits_{i=1}^nh(i)-\sum\limits_{d=2}^ng(d)S(\dfrac{n}{d})$
$g(1)S(n)=\sum\limits_{i=1}^n(f*g)(i)-\sum\limits_{d=2}^ng(d)S(\dfrac{n}{d})$
如果选取了合适的$g$使$f*g$的前缀和便于计算的话，就能整除分块递归计算$S(\dfrac{n}{d})$了。
应用
莫比乌斯函数
我们知道$\mu* 1=e$，显然$e$的前缀和就是$1$。
把$g$配为$1$，就有$S(n)=1-\sum\limits_{d=2}^nS(\dfrac{n}{d})$
欧拉函数
欧拉函数有$\varphi*1=id$，$id$前缀和就是自然数前$n$项和。
于是$S(n)=\sum\limits_{i=1}^ni-\sum\limits_{d=2}^nS(\dfrac{n}{d})$
奇怪的欧拉函数
求$\sum\limits_{i=1}^ni\varphi(i)$。
要消去烦人的$i$，给$i\varphi(i)$卷上$id$：
$i\varphi(i)*id=\sum\limits_{d|n}d\varphi(d)\dfrac{n}{d}=n\sum\limits_{d|n}\varphi(d)=n^2$
$S(n)=\sum\limits_{i=1}^ni^2-\sum\limits_{d=2}^ndS(\dfrac{n}{d})$
实现
一般是先线筛出部分前缀和，再配合上记忆化。
以$\mu$为例：
#define maxn 10000001
#define inf 0x3f3f3f3f
const int Mod = 1e6 + 7;
struct hash{
int h[Mod],d[Mod],s[Mod],nex[Mod],cnt;
void insert(int x,int y){
s[++cnt]=x,x%=Mod,nex[cnt]=h[x],d[h[x]=cnt]=y;
}
int find(int x){
for(register int i=h[x%Mod];i;i=nex[i])
if(s[i]==x)return d[i];
return -inf;
}
}mmu;//哈希记忆化
int mu[maxn],prime[maxn>>2],cnt;
bool is[maxn];
void sieve(){
is[1]=mu[1]=1;
for(register int i=2;i<maxn;++i){
if(!is[i])prime[++cnt]=i,mu[i]=-1;
for(register int j=1;j<=cnt&&i*prime[j]<maxn;++j){
is[i*prime[j]]=1;
if(i%prime[j]==0){mu[i*prime[j]]=0;break;}
mu[i*prime[j]]=-mu[i];
}
}
for(register int i=2;i<maxn;++i)mu[i]+=mu[i-1];
}//筛出前maxn的前缀和
int smu(int n){
if(n<maxn)return mu[n];
int ans=mmu.find(n);
if(ans!=-inf)return ans;
ans=1;
for(register int l=2,r;l<=n;l=r+1){
r=n/(n/l);
ans-=(r-l+1)*smu(n/l);
}
mmu.insert(n,ans);
return ans;
}
vim没有c++11开不了unordered_map只好手写哈希
还有种更高端的记忆化。
由于求的前缀和都是$N$的约数，开一个$\sqrt{N}$大小的数组$mmu$。
若$n\le \sqrt{n}$返回$mmu[n]$，否则返回$mmu[\sqrt{N}+N/n]$。
然而每次都要清空$mmu$数组。
复杂度
不提前线筛的话复杂度是$O(n^{\frac{3}{4}})$
如果线筛出前$n^{\frac{2}{3}}$的前缀和的话是$O(n^{\frac{2}{3}})$
不会证（理直气壮）
还有个很有意思的东西：
整除分块套杜教筛：
for(register int l=1,r;l<=n;l=r+1){
r=n/(n/l);
ans+=(smu(r)-smu(l-1))*(n/l);
}
上面这个的复杂度是$O(\sqrt{n}+n^{\frac{2}{3}})$的！
由于每个块的右端点都是$n/(n/l)$，而$l-1$相当于上一个块的右端点，我们可以看做取遍了$\left\lfloor\dfrac{n}{i}\right\rfloor$。而在杜教筛中求$S(n)$的时候已经把$S(\left\lfloor\dfrac{n}{i}\right\rfloor)$都算过了，所以记忆化之后这些值都可以$O(1)$得到，整个复杂度就是加起来的。
同理，杜教筛套杜教筛的复杂度为$O(n^{\frac{2}{3}})$。
水题
Problem b
其实是个容斥，也算是二维前缀和。
设$f(n,m)=\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=k]$
求$\sum\limits_{i=a}^b\sum\limits_{j=c}^{d}[gcd(i,j)=k]$
我们暴力展开或者把它想象成二维平面上的一个矩形，就变成了$f(b,d)-f(b,c-1)-f(a-1,d)+f(a-1,c-1)$
然后就是栗子了。
YY的GCD
求$\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)\in prime]$
暴力枚举质数：
$=\sum\limits_{a\in prime}\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=a]$
套路地变换：
$=\sum\limits_{a\in prime}\sum\limits_{i=1}^{\lfloor\frac{n}{a}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{a}\rfloor}\sum\limits_{d|gcd(i,j)}\mu(d)$
$=\sum\limits_{a\in prime}\sum\limits_{d=1}^{\lfloor\frac{n}{a}\rfloor}\left\lfloor\dfrac{n}{ad}\right\rfloor\left\lfloor\dfrac{m}{ad}\right\rfloor\mu(d)$
这样复杂度还是太高。
设$k=ad$，显然$a|k$。改为枚举$k$：
$=\sum\limits_{a\in prime}\sum\limits_{k=1}^n[a|k]\left\lfloor\dfrac{n}{k}\right\rfloor\left\lfloor\dfrac{m}{k}\right\rfloor\mu(d)$
变换求和顺序：
$=\sum\limits_{k=1}^n\left\lfloor\dfrac{n}{k}\right\rfloor\left\lfloor\dfrac{m}{k}\right\rfloor\sum\limits_{a\in prime}[a|k]\mu(d)$
这样前面的可以整除分块，后面那一坨可以预处理。对于每个质数，给它的倍数加上$\mu$即可。
约数个数和
Crash的数字表格
选数
这个题直接把我送去学杜教筛了。
个人习惯把$H$看作$R$，把$N$看作$n$。
求$\sum\limits_{i_1=L}^R\sum\limits_{i_2=L}^R···\sum\limits_{i_n=L}^R[gcd(i_1,i_2,…i_n)=k]$
如果玩套路的话感觉有点麻烦，试试正规反演：
先转化一下，枚举$k$的倍数，这样$R=\lfloor\dfrac{R}{k}\rfloor,L=\lceil\dfrac{L}{k}\rceil$
就成了$\sum\limits_{i_1=L}^R\sum\limits_{i_2=L}^R···\sum\limits_{i_n=L}^R[gcd(i_1,i_2,…i_n)=1]$
设$f(d)=\sum\limits_{i_1=L}^R\sum\limits_{i_2=L}^R···\sum\limits_{i_n=L}^R[gcd(i_1,i_2,…i_n)=d],g(d)=\sum\limits_{d|n}f(n)$
考虑$g$的含义，就是有$n$个值域为$[L,R]$的数，它们的$gcd$为$d$的倍数。
$g(d)=\left(\left\lfloor\dfrac{R}{d}\right\rfloor-\left\lfloor\dfrac{L-1}{d}\right\rfloor\right)^{n}$
反演得：$f(d)=\sum\limits_{d|n}\mu(n)g(\dfrac{n}{d})$
答案为$f(1)=\sum\limits_{i=1}^R\mu(i)g(i)$
后面$g$可以整除分块，$R$达到$1e9$要杜教筛。复杂度为$O(n^{\frac{2}{3}}+\sqrt{n}\log n)$。
于神之怒加强版
上面那道题送我去学了杜教筛，这道题送我去重学了遍线筛。
推法很套路，最后求的是$\sum\limits_{T=1}^n\left\lfloor\dfrac{n}{T}\right\rfloor\left\lfloor\dfrac{m}{T}\right\rfloor\sum\limits_{d|T}d^k\mu(\dfrac{T}{d})$
然后就是筛$f(T)=\sum\limits_{d|T}d^k\mu(\dfrac{T}{d})$。$n$有$5e6$，简单的$O(n\log n)$筛法不好过了。
显然$f=\mu*id^k$是个积性函数，可以考虑线筛。
对于质数$p$：
$f(p)=p^k-1$
$f(p^m)=(p^m)^k-(p^{m-1})^k$
我们要推到$f(p^{m+1})=(p^m)^k-(p^{m-1})^k=(p^k-1)(p^k)^m=f(p)(p^k)^m$
对于所有仅有一个质因子的数维护函数$g(p^m)=(p^k)^m$，这个是可以推上去的。
则$f(p^{m+1})=f(p)g(p^m)$。
考虑到我们仅对每个质数做快速幂，复杂度还是$O(\dfrac{n}{\ln n}\log k)=O(n)$的。
线筛代码：
#define maxn 5000001
const int mod = 1000000007;
int g[maxn],f[maxn],low[maxn],prime[maxn>>2],cnt;
bool is[maxn];
void sieve(){
f[1]=is[1]=1;
for(register int i=2;i<maxn;++i){
if(!is[i])prime[++cnt]=i,f[i]=quickpow(i,k)-1,g[i]=f[i]+1,low[i]=i;
for(register int j=1;j<=cnt&&i*prime[j]<maxn;++j){
is[i*prime[j]]=1;
if(i%prime[j]==0){
low[i*prime[j]]=low[i]*prime[j];
if(low[i]==i)g[i*prime[j]]=1ll*g[i]*g[prime[j]]%mod,f[i*prime[j]]=1ll*g[i]*f[prime[j]]%mod;
else f[i*prime[j]]=1ll*f[i/low[i]]*f[low[i]*prime[j]]%mod;
break;
}
low[i*prime[j]]=prime[j];
f[i*prime[j]]=1ll*f[i]*f[prime[j]]%mod;
}
}
}
简单的数学题
数表
求$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sigma(gcd(i,j))[\sigma(gcd(i,j))\le a]$
套路推完式子长这样：$\sum\limits_{T=1}^n\left\lfloor\dfrac{n}{i}\right\rfloor\left\lfloor\dfrac{m}{i}\right\rfloor\sum\limits_{d|T,\sigma(d)\le a}\mu(\dfrac{T}{d})\sigma(d)$
所有数按$\sigma$排序，把询问离线下来按$a$排序。
处理每个询问前依次把$\sigma(i)\le a$的数的贡献算上。
这样就是若干个单点加和区间查，树状数组维护即可。
模数是$2^{31}$可以自然溢出$int$。
复杂度$O(n\log^2n+T\sqrt{n}\log n)$
