---

一、定义

1.内容及解释

$\mu (n)=\{\begin{array}{ll}1& n=1\\ (-1{)}^k& n=p_1\ast p_2......p_k\\ 0& otherwise\end{array}$

当$n=1$时，$\mu (1)=1$；
当$n$被唯一分解后，质因子的指数只为1时，k为质因子的个数，$\mu (n)=(-1{)}^k$；
当$n$被唯一分解后，含有平方因子时(存在质因子指数大于等于2)，$\mu (n)=0$

2.应用场景

一般都应用于莫比乌斯反演中作为指数，有个大概的印象就好。
若存在$F(n)={\sum }_{d|n}f(d)$,则有$f(n)={\sum }_{d|n}\mu (d)F(\frac{n}{d})$

---

二、性质

1.积性函数·$gcd(a,b)=1,\mu (ab)=\mu (a)\mu (b)$

简单证明

当$gcd(a,b)=1$时，说明$a,b$不存在唯一分解后不存在公共的质因子，即每个质因子的指数不会发生改变。

若在$a,b$中存在一个质因子指数大于等于2，那么在$ab$依旧会存在该质因子指数大于等于2，故满足$\mu (a)\ast \mu (b)=\mu (ab)=0$；

若在$a,b$中质因子指数均为1(可分解出质因子，均不会为1)，那么$ab$中质因子的指数也均为1，依旧满足$\mu (a)\ast \mu (b)=(-1{)}^u\ast (-1{)}^v=(-1{)}^{uv}=\mu (ab)$;

若在$a,b$中至少存在一个为1，令$a=1$，那么$\mu (a)\ast \mu (b)=1\ast \mu (b)=\mu (ab)$

2.${\sum }_{d|n}\mu (d)=\{\begin{array}{ll}1& n=1\\ 0& n>1\end{array}$

简单证明

当$n=1$时，成立；

当$n>1$时，可以对$n$进行唯一分解：$n=p_1^{a_1}\ast p_2^{a_2}......p_k^{a_k}$

统计$\mu (d)$时，若约数$d$含有质因子的指数大于等于2，$\mu (d)=0$，所以质因子的指数只需要关注0跟1.
质因子个数为k个，那么有r个质因子所组成的约数d的组合为$C_k^r$

${\sum }_{d|n}\mu (d)=C_k^0-C_k^1+C_k^2......(-1{)}^k{C}_k^k={\sum }_{i=0}^k(-1{)}^i{C}_k^i$

参考二项式定理：$(x+y{)}^n={\sum }_{i=0}^n{C}_n^i{x}^i{y}^{n-i}$

此时可以把$x$替换为-1，把$y$替换为1，也就得到了${\sum }_{d|n}\mu (d)=(-1+1{)}^k=0$，成立。

---

三、筛法

1.求单个函数值

就是根据定义来计算单个函数值。

int mus(int n){
    
    int cnt,k=0;
    for(int i=2;i*i<n;i++){
    
        if(n%i){
    
            continue;
        }
        cnt=0;
        k++;
        while(n%i==0){
    
            n/=i;
            cnt++;
        }
        if(cnt>=2){
    
            return 0;
        }
 
    }
    if(n!=1){
    
        k++;
    }
    return k%2?-1:1;
}

2.线性筛法

利用积性函数性质，$gcd(a,b)=1,\mu (ab)=\mu (a)\mu (b)$，再结合欧拉筛法，线性时间内求出1到n的莫比乌斯函数值。

typedef long long ll;
const int N=5e+5;
int tot;
int vis[N];//
int mu[N];//
int pri[N];
// 莫比乌斯函数线性筛
void allmus(int n){
    // 欧拉筛的扩展
	tot=0;
	mu[1]=1;
	pri[0]=pri[1]=1;
	for(int i=2;i<n;i++){
    
		if(!vis[i]){
    
			pri[++tot]=i; 
			mu[i]=-1;
		}
		for(int j=1;j<=tot&&i*pri[j]<n;j++){
    
			vis[i*pri[j]]=1;
			if(i%pri[j]==0){
    
				mu[i*pri[j]]=0;//说明i中含有质因子pri[j],所以i*pri[j]对于质因子pri[j]来说，指数大于1，属于otherwise 
				break;
			}
			mu[i*pri[j]]=-mu[i];//说明满足互质关系，可以直接利用积性函数性质，为了减少操作，取负号即可 
		}
	}
}

---

四、例题

1.完全平方数（容斥+二分）

完全平方数

大意：

此时要默认1不属于完全平方数，否则题目就没法做了，题目筛去了完全平方数以及其倍数，也就是筛去了唯一分解后含质因子指数大于等于2的数，问剩余的数中第k个数。

分析：

由题可知，满足条件的数除了1以外，其余的数唯一分解后的质因子的指数都为1.

先根据题目k的范围来看，$k<=10^9$，意味着我们不能暴力的使用筛法把结果都筛出来，那么我们的思路就是用二分。

若存在一个函数$Q(x)$可以计算出$[1,x]$内满足要求的数，那么在计算出了二分上界和下界的基础上，就可以二分出第一个满足$Q(x)=k$的$x$了。

（1）求解$Q(x)$

$Q(x)$表示范围内满足条件的所有数，$F(x)$表示范围内不满足条件的所有数.
所以有$Q(x)=x-F(x)$

计算$F(x)$的时候，需要计算每个质因数的平方的倍数（即4的倍数，9的倍数……），这里就满足了我们应用容斥原理的条件——求并集

$F(x)=$一个质因数的平方数的倍数的数的个数-为两个不同质因数乘积的平方数的倍数的数的个数+三个不同质因数乘积的平方数的倍数的数的个数……

有意思的是，在这里每一项的系数都与相关质因数的个数有关，而且恰与$\mu (x)$的定义相反，我们再改写为$Q(x)$的形式：
$Q(x)=x-(一个质因数的平方数的倍数的数的个数)+(为两个不同质因数乘积的平方数的倍数的数的个数)-(三个不同质因数乘积的平方数的倍数的数的个数)\dots \dots$
此时每一项的系数就与$\mu (x)$完全对应了.

而且这里所使用的不同质因数乘积满足小于等于$\sqrt{x}$就足以筛去$[1,x]$内所有不满足条件的数了。
上式就可以直接转化为：$Q(x)={\sum }_{i=1}^{\lfloor \sqrt{x}\rfloor }\mu (x)\lfloor \frac{x}{i^2}\rfloor$
以$i=6$为例，$\mu (6)=1$,所以是加上$[1,x]$内36的倍数的个数。
关于这个式子的求解可以参考博客：整除分块小结，可以在$O(\sqrt{\sqrt{n}})$内计算出$Q(x)$

(2)估计二分的上下界

下界：由于第k个数一定是大于等于k的，为了稳妥和方便，不妨设$l=k-1$，
上界：至于上界不好估计，需要手动测试一下，当$r=2k+1$，可以发现用最大的来测试也仍旧满足$Q(r)>k$

所以以$l=k-1,r=2\ast k+1$

代码：

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
const int N=60005;

int k;
int tot;
int vis[N];//
int mu[N];//
int pri[N];
// 莫比乌斯函数线性筛
void mus(int n){
    // 欧拉筛的扩展
	tot=0;
	mu[1]=1;
	pri[0]=pri[1]=1;
	for(int i=2;i<n;i++){
    
		if(!vis[i]){
    
			pri[++tot]=i; 
			mu[i]=-1;
		}
		for(int j=1;j<=tot&&i*pri[j]<n;j++){
    
			vis[i*pri[j]]=1;
			if(i%pri[j]==0){
    
				mu[i*pri[j]]=0;//说明i中含有质因子pri[j],所以i*pri[j]对于质因子pri[j]来说，指数大于1，属于otherwise 
				break;
			}
			mu[i*pri[j]]=-mu[i];//说明满足互质关系，可以直接利用积性函数性质，为了减少操作，取负号即可 
		}
	}
}

bool check(int x){
    
    int l=1,r;
    int mx=sqrt(x);
    ll cnt=0;
    while(l<=mx){
    //整除分块 
        int p=x/(l*l);
        r=sqrt(x/p);
        cnt+=(ll)(mu[r]-mu[l-1])*(x/(l*l));
        l=r+1;
    }
    return cnt>=k;
}

int main(){
    
   	int t;
	cin>>t; 
    mus(N);
    
 	for(int i=2;i<=N;i++)mu[i]+=mu[i-1];//便于求区间和，方便后面的整除分块 
 	
    while(t--){
    
        cin>>k;
        ll l=k-1,r=k*2+1;
        while(r-l>1){
    
            ll mid=l+r>>1;
            if(check(mid)) r=mid;
            else l=mid;
        }
        cout<<r<<endl; 
    }
    return 0;
}

2.GCDispower

GCDispower

可能会填坑。

---