容斥与莫比乌斯函数
容斥原理：
介绍：设集合\(S_1\sim S_n\),记\(|S_i|\)表示集合\(S_i\)的大小，设\(\cup\)表示集合的并集运算，\(\cap\)表示集合的交集运算，则
\[\left|\bigcup_{i=1}^nS_i\right|=\sum_{i=1}^n|S_i|-\sum_{1\le i<j\le n}|S_i\cap S_j|+\sum_{1\le i<j<k\le n}|S_i\cap S_j\cap S_k|-…+(-1)^{n+1} \left | \bigcap_{i=1}^nS_i \right| \]所以由容斥原理可以得到之前的多重集的组合数公式：
设集合\(\mathbb{S}={\lbrace n_1·a_1,n_2·a_2,n_3·a_3…n_k·a_k\rbrace}\)是由\(n_1\)个\(a_1\)……组成的多重集，\(n=\sum_{i=1}^kn_i\)
则从该集合中选出\(r(r\le n)\)个数组成的不同的多重集数量为：
对于容斥原理在代码中的实现：我们可以枚举\(x\in [0,2^k-1]\),将x内的含1的位提取出来，根据奇偶性判断是加还是减，特别的，我们令x=0代表\(C_{k+r-1}^{k-1}\)
Mobius函数
莫比乌斯函数是一个容斥系数，与容斥原理息息相关
定义：设\(x\)被算术基本定理分解为：\(\prod_{i=1}^np_i^{c_i}\)
\[\mu(x) = \begin{cases} 0 & \exists i\in[1,n],c_i\ge 2\\ 1 & n \bmod 2=0,\forall i\in[1,n],c_i=1\\ -1 & n \bmod 2=1,\forall i\in[1,n],c_i=1\\ \end{cases} \]则称\(\mu(x)\)为\(u\)的\(mobius\)函数
对于mobius函数的求法：
如果只是求一个数的莫比乌斯函数，分解质因数即可，若是求\(1\sim N\)的，则使用埃拉托尼斯筛法计算
for(int i=1;i<=n;i++)mui[i]=1,vis[i]=0;
for(int i=2;i<=n;i++){
if(vis[i])continue;
mui[i]=-1;
vis[i]=1;
for(int j=2;j*i<=n;j++){
mui[i*j]*=-1;
if(j%i==0)mui[i*j]=0;
vis[i*j]=1;
}
}
性质:
1.对于任意正整数n，\(\sum_{d|n}\mu(i)=[n=1]\)
2.若\(\gcd(a,b)=1\),则\(\mu(ab)=\mu(a)\mu(b)\)
莫比乌斯函数与容斥原理的关系：
即对\(1\sim N\)应用容斥原理，则每个数的莫比乌斯函数决定了那个数的系数
随意扔一道例题：
ZAP-Queries
[POI2007]ZAP-Queries
题目描述
密码学家正在尝试破解一种叫 BSA 的密码。
他发现，在破解一条消息的同时，他还需要回答这样一种问题：
给出 \(a,b,d\)，求满足 \(1 \leq x \leq a\)，\(1 \leq y \leq b\)，且 \(\gcd(x,y)=d\) 的二元组 \((x,y)\) 的数量。
因为要解决的问题实在太多了，他便过来寻求你的帮助。
输入格式
输入第一行一个整数 \(n\)，代表要回答的问题个数。
接下来 \(n\) 行，每行三个整数 \(a,b,d\)。
输出格式
对于每组询问，输出一个整数代表答案。
数据规模与约定
对于全部的测试点，保证 \(1 \leq n \leq 5 \times 10^4\)，\(1 \leq d \leq a,b \leq 5 \times 10^4\)。
分析：
求有多少对二元组\((x,y)\)满足\((x\le a,y \le b)\)并且\(gcd(x,y)=k\)，等价于求有多少对二元组\((x,y)\)满足\((x\le \frac{a}{k},y \le \frac{b}{k})\)并且\(x,y\)互质
设\(D[a,b,k]\)表示满足\(x\le a,y\le b\)并且\(k|gcd(x,y)\)的二元组有多少对，显然，只需要\(x,y\)是\(k\)的倍数即可，而\(1\sim a\)中k的倍数有\(\lfloor\frac{a}{k}\rfloor\)个，b同理，则我们很容易就可以得出\(D[a,b,k]=\lfloor\frac{a}{k}\rfloor\lfloor\frac{b}{k}\rfloor\)
设\(F[a,b]\)表示满足\(x\le a,y le b\)的二元组\((x,y)\)有多少对，则有：
\[F[a,b]=\sum_{i=1}^{\min(a,b)}\mu(i)\times D[a,b,i] \]上式含义：当\(i=1\)的时候\(D[a,b,1]\times \mu(1)\),而\(\mu(1)=1\)，所以此时就相当于是加上了所有的二元组\(a\times b\),应当减去\(2,3,5,7……\)的倍数，但是6，10等就被减去了两次需要在加回来一次……以此类推便可以确定对于每个数加减的系数都是\(\mu\)函数
又联系我们之前学习的数论分块的知识
\(\lfloor\frac{a}{k}\rfloor\lfloor\frac{b}{k}\rfloor\)这是呈段状的
\(\forall i\in [x,\min(\lfloor\frac{a}{\lfloor\frac{a}{x}\rfloor}\rfloor,\lfloor\frac{b}{\lfloor\frac{b}{x}\rfloor}\rfloor)],\lfloor\frac{a}{k}\rfloor\lfloor\frac{b}{k}\rfloor\)的值都相等，我们预处理\(\mu\)函数的前缀和即可直接累加这一段答案
#define int long long
int T,n,a,b,d,mobius[50005],sum[50005];
bool vis[50005];
void init(){
for(int i=1;i<=50000;i++)mobius[i]=1;
for(int i=2;i<=50000;i++){
if(!vis[i]){
mobius[i]=-1;
for(int j=2;j*i<=50000;j++){
vis[j*i]=1;
mobius[i*j]= j%i==0?0:-mobius[i*j];
}
}
}
for(int i=1;i<=50000;i++)sum[i]=sum[i-1]+mobius[i];
}
int get(int a,int x){
return a/(a/x);
}
signed main(){
init();
scanf("%lld",&T);
while(T--){
int ans=0;
scanf("%lld%lld%lld",&a,&b,&d);
a/=d,b/=d;
n=min(a,b);
for(int l=1,r;l<=n;l=r+1){
r=min(n,min(get(a,l),get(b,l)));
ans+=(sum[r]-sum[l-1])*(a/l)*(b/l);
}
printf("%lld\n",ans);
}
return 0;
}
莫比乌斯反演定理
仅作了解，tg无需掌握
设函数\(f(x),g(x)\)是定义在正整数集上的两个函数
形式1
若函数\(f(x),g(x)\)满足
\[f(n)=\sum_{d|n}g(d)=\sum_{d|n}g(\frac{n}{d}) \]则：
\[g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})=\sum_{d|n}\mu(\frac{n}{d})f(d) \]形式2
若函数\(f(x),g(x)\)满足：
\[f(n)=\sum_{n|d}g(d)=\sum_{n|d}g(\frac{n}{d}) \]则有
\[g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)=\sum_{n|d}\mu(d)f(\frac{d}{n}) \]推一个大佬博客“浅谈”莫反
标签：lfloor,le,frac,sum,容斥,莫反,mu,rfloor,简单 From： https://www.cnblogs.com/oierpyt/p/16939977.html