今天有空来专门总结一下代码模版，顺便定制一张代码模版鼠标垫，哦吼！！！

↑这就是预期效果啦！！！

下面开始总结算法模版：

素数筛（线性筛）

时间复杂度 \(O(N)\)

void primes(int n){//线性筛区间[1,n]的素数 
	memset(isprime,true,sizeof(isprime));  //全部标记为素数 
    isprime[1]=false;m=0;
	for(int i=2;i<=n;i++){
		if(isprime[i]) prime[++m]=i;
		for(int j=1;j<=m;j++){
			if(prime[j]>n/i) break;//i*prime[j]超出n的范围 
			isprime[i*prime[j]]=false;
		    if(i%prime[j]==0) break;//保证prime[j]是i的最小质因子 
		}
	}
}

Tarjan求强联通分量

void tarjan(int u){
	dfn[u]=low[u]=++tim;
	s.push(u);
	vis[u]=1;
	for(int e=fir[u];e;e=nex[e]){
		int v=to[e];
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(vis[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		cnt++;
		int v;
		do{
            v=s.top();s.pop();
			vis[v]=0;
			fl[v]=cnt;sl[cnt]++;
		}while(v!=u)
	}
}

LCA倍增

void Init(int u,int father){
	dep[u]=dep[father]+1;
	for(int i=0;i<=16;i++)
		f[u][i+1]=f[f[u][i]][i];
	for(int e=first[u];e;e=Next[e]){
		int v=to[e];
		if(v==father) continue; 
		f[v][0]=u;   //v的父亲是u 
		Init(v,u); 
	}
}
int Lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);//保证x深度更大 
	for(int i=17;i>=0;i--){
		if(dep[f[x][i]]>=dep[y]) x=f[x][i];
		if(x==y) return x;  
	}
	for(int i=17;i>=0;i--){
		if(f[x][i]!=f[y][i]){ 
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];//最后跳到了lca的下面一个 
}

树状数组

动态维护前缀和，支持单点，区间更新和查询

int lowbit(int i){
	return i & (-i);
}
void update(int j,int i){
	while(i<=n){
		tree[i]+=j;
		i+=lowbit(i);
	}
}
int query(int i){
	int sum=0;
	while(i>0){
		sum+=tree[i];
		i-=lowbit(i);
	}	
	return sum;
}

欧几里得（GCD）

int gcd(int a,int b){ //欧几里得（辗转相除） 
	if(b==0) return a;
	else return gcd(b,a%b);
}

快速幂

int fastpower(int a,int b){
	int ans=1;
	while(b>0){
		if(b&1) ans=(ans*a)%mod;
		b=b>>1;
		a=(a*a)%mod;
	}	
	return ans;
}

并查集

int getfather(int x){
	if(fa[x]==x) return x;
	fa[x]=getfather(fa[x]);
	return fa[x];
}
void merge(int x,int y){
	int fx=getfather(x);
	int fy=getfather(y);
	fa[fx]=fy;
}

KMP

void getNext() //计算Next数组
{
	int j=1,k=0;
	Next[1]=0;
	while(j<lent){
		if(k==0||t[j]==t[k])
			Next[++j]=++k;
		else k=Next[k];
	}
}