代码模板
今天有空来专门总结一下代码模版，顺便定制一张代码模版鼠标垫，哦吼！！！
↑这就是预期效果啦！！！
下面开始总结算法模版：
素数筛（线性筛）
时间复杂度 \(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];
}
}