C++板子

(目前学到的板子 不全/自用)

素数筛

//时间复杂度O(nloglogn)
bool isnp[MAXN]={1,1}; //is not prime: 不是素数
void init(int n)
{
    for (int i=2;i*i<=n;i++)
        if (!isnp[i])
            for (int j=i+i;j<=n;j+=i)
                isnp[j] = 1;
}

快读

inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')w*=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        //s=(s<<1)+(s<<3)+ch-'0';
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*w;
}

二分

返回左端点

int ef_l(int l, int r)
{
    while(l<r)
    {
        int m=l+r>>1;
        if(q[m]>=x)r=m;
        else l=m+1;
        /*
        如果 q[m] < x
        说明 [l,mid] 范围内均小于 x
        则令 l = m + 1
        */
    }
    return l;
}

//不需要判断+-模板
int efl(int l,int r,int c){
    while(r-l>4){
        int m=l+r>>1;
        if(a[m]>=c)r=m;
        else l=m;
    }
    for(int i=l;i<=r;i++)
        if(a[i]==c)return i;
    return -1;
}

返回右端点

int ef_r(int l,int r)
{
    while (l<r)
    {
        int m=(l+r+1)>>1;
        if(q[m]<=x)l=m;
        else r=m-1;
    }
    return l;
}

//不需要判断+-模板
int efr(int l,int r,int c){
    while(r-l>4){
        int m=l+r+1>>1;
        if(a[m]>c)r=m;
        else l=m;
    }
    for(int i=r;i>=l;i--)
        if(a[i]==c)return i;
    return -1;
}

邻接表

const int N=100010;
int e[N],ne[N],h[N],idx;
void add(int a,int b)//添加一条a->b的边
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
// 初始化
idx=0;
memset(h,-1,sizeof h);

快速幂

int qmi(int a,int k,int p)
{
    int res=1%p;//防止 k为0 p为1的情况
    while (k)
    {
        if(k&1)res=1ll*res*a%p;//k的个位是1 乘一次a
        a=1ll*(a*a)%p;//求a的平方(方便下次循环使用)
        k>>=1;//右移1 去掉个位
    }
    return res;
}