并查集、快速幂 and 线性筛素数。

并查集

描述

如题，现在有一个并查集，你需要完成合并和查询操作。

也就是说我们要维护集合的操作，那该怎么做呢？

实现

我们用 $fa_x$ 表示 $x$ 的从属关系。（一开始 $fa_x=x$，也就是自己一个元素一个集合）

将 $x$ 所属的集合和 $y$ 所属的集合合并时，即让 $fa_y$ 变为 $x$ 所属集合的最顶部的 $fa_{top}$。（也可以理解成连上去）

代码如下：

int Find(int a){
	if(a==fa[a])return a;
	return Find(fa[a]);
}

fa[y]=Find(x);

路径压缩

在Find(a)的过程中将路径上的所有点直接连到最高点。（可以理解成从一条链压缩成菊花图）

代码如下：

int Find(int a){
	if(a==fa[a])return a;
	return fa[a]=Find(fa[a]);
}

快速幂

描述

快速求幂awa

实现

就是指数除2底数平方。

直接上代码：

int fpower(int x,int y,int mod){
	int ans=1;
	while(y){
		if(y%2)ans=ans*x%mod;//奇数单独处理
		x=x*x%mod;
		y>>=1;
	}
	return ans;
}

线性筛素数

描述

如题，给定一个范围 n，有 q 个询问，每次输出第 k 小的素数。

最朴素的筛法：埃氏筛。

每次将素数的倍数筛去，因为会有很多被重复筛的数，最好也只能做到 $O(n log log n)$。

在 $10^8$ 这个阶级会超时。

所以我们考虑下面这种做法。

分析

欧拉筛

考虑每个合数只被筛一次。

原则：这个合数只会被它的最大非自身因数（对应最小质因数）筛。

每次循环已经筛过的质数去乘当前的数，当这个数为质数的倍数时停止。

此时这个质数为它的最小质因数，符合原则。

但下一个质数不符合，这个合数可以拆分出为比这个质数更小的质数（上一个）。

代码实现如下：

for(int i=2;i<=n;i++){
	if(!flag[i])prime[++cnt]=i;
	for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
		flag[i*prime[j]]=1;
		if(!i%prime[j])break;
	}
}