//最大公约数 
核心原理就是a和b的公约数等于b和a%b的公约数 
int gcd(int a,int b)
{
	if(b) return gcd(b,a%b);
	return a;
} 
int gcd(int a,int b)
{
	return b?gcd(b,a%b):a;
}


//分解质因数
 
map<int,int> h;
for(int i=2;i*i<=a;i++) //枚举小的因子 
{
	while(a%i==0)
	{
		h[i]++; //i的次方数增加 
		a/=i;
	 }
	 
}
if(a>1) //剩余的一个数本身是质数 
{
	h[a]++;
}



//试除法判定质数

bool st=true;
if(n<2)
{
	st=false;
}
for(int i=2;i<=n/i;i++)
{
	if(n%2==0)
	{
		st=false;
	}
}
//st==true 表示n是质数，否则不是质数

 
//埃式筛质数
for(int i=2;i<=n;i++) //从前往后看每个位置 
{
	if(a[i]==0) //当前位置没有被标记 
	{
		for(int j=2*i;j<=n;j+=i) //标记i的倍数 
		{
			a[j]=1;
		}
	}
} 

//线性筛质数
bool st[N],idx;
vector<int> p;
/*
1.标记的过程
如果i不是p[j]的倍数,那么p[j]是小于等于i的，相等于i*p[j]是被p[j]标记的，p[j]是i*p[j]的最小质因子
如果i是p[j]的倍数，那么p[j]是i的最小质因子，同时也是i*p[j]的最小质因子
核心原理:每个数一定是被最小的质因子标记的
*/
void get(int n)
{
    for(int i=2;i<=n;i++) //枚举所的数
    {
        if(!st[i]) p.push_back(i); //当前数没有被标记过，说明是质数
        for(int j=0;p[j]*i<=n;j++) //枚举i的质数倍
        {
            st[i*p[j]]=1; //标记
            if(i%p[j]==0) //如果p[j]是i的因子，那么标记跳出循环，
            {
                break;
            }
        }
    }
} 

//试除法求约数

vector<int> v;
for(int i=1;i<=x/i;i++) //枚举小因子
{
    if(x%i==0) //存在小因子 
    {
        v.push_back(i);
        if(x/i!=i) //大小因子不同
        {
            v.push_back(x/i);
        }
    }
}

//倍数法求约数
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=n/i;j++) //枚举i的j倍 
    {
        g[i*j].push_back(i); //将i放到i的倍数后面 
    }
} 

//容斥原理(奇数增加，偶数减少) 

for(int i=1;i<(1<<m);i++) //枚举所有的选择 
{
    int cnt=0;
    LL t=1;
    for(int j=0;j<m;j++)
    {
        if(i>>j&1) //选择了第j个数 
        {
            cnt++; //数的个数增加一个 
            t=t*p[j]; //计算当前乘积 
        }
        if(t>n) //已经越界 
        {
            t=-1;
            break;
        }
    }
    if(t==-1) continue; //越界 
    if(cnt%2) res+=n/t; //奇数增加 
    else res-=n/t; //偶数减少 
} 

//快速幂
LL qmi(LL a,LL b,LL p)
{
	LL res=1%p; //先取余 
	while(b)    //还有值 
	{
		if(b&1)  //当前位需要累乘 
        {
            res=res*a%p;
        }
		a=a*a%p; //计算下一位 
		b=b>>1; //删除当前位 
	}
	return res;
} 

//欧拉函数(1到n中和n互质的数的个数) 
for(int i=2;i*i<=x;i++) //分解质因数 
{
	if(x%i==0)
	{
		res=res/i*(i-1);
		while(x%i==0)
		{
			x/=i;
		}
	}
}
if(x>1) //存在质因子 
{
	res=res/x*(x-1);
}


//筛法求欧拉函数 

long long get(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) //质数 
        {   
            p[cnt++]=i; //质数增加 
            phi[i]=i-1; //欧拉函数值 
        }
        for(int j=0;p[j]*i<=n;j++)
        {
            st[i*p[j]]=1; //标记 
            if(i%p[j]==0)
            {
                //phi[i*p[j]]相对于phi[i]只是n值发生了变化 
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            else
            {
                //phi[i*p[j]]相对于phi[i]n值和质因子都发生了变化 
                phi[i*p[j]]=phi[i]*(p[j]-1);
            }
        }
    }
    long long res=0;
    for(int i=1;i<=n;i++) //累加1到n的欧拉函数值 
    {
        res=res+phi[i];
    }
    return res;
}

//约数个数

map<int,int> h; //统计所有数乘积分解质因数的结果
while(n--) 
{
    int x;
    cin>>x;
    for(int i=2;i<=x/i;i++) //对于每个数x分解质因数
    {
        while(x%i==0)
        {
            h[i]++;
            x/=i;
        }
    }
    if(x>1) h[x]++;
}
LL res=1;
for(auto it:h) //遍历整个map
{
    int a=it.first,b=it.second; //获取底数和指数
    res=res*(1+b)%P; //使用乘法原理计算方案数
} 

// 约数和
map<int,int> h; //储存n个数乘积分解质因数的结果 
cin>>n;
while(n--)
{
    int x;
    cin>>x;
    for(int i=2;i<=x/i;i++) //分解质因数 
    {
        while(x%i==0)
        {
            h[i]++;
            x/=i;
        }
    }
    if(x>1) h[x]++;
}
LL res=1;
for(auto it:h)
{
    int a=it.first,b=it.second; //获得底数和指数 
    long long t=1;//t=a^0+a^1+a^2...a^b 
    for(int i=1;i<=b;i++)
    {
        t=(t*a+1)%P;
    }
    res=res*t%P;
}

//排列
while(true)
{
    int k=n;
    while(k-1>=1&&a[k-1]>a[k]) k--; //找到下降的位置
    if(k-1==0) break; //越界了
    k=k-1; //下降的位置
    int t=n; //从后找到第一个大于它的元素
    while(a[k]>a[t]) t--; //小于就一直累加
    swap(a[k],a[t]); //和最后一个比他大的交换
    reverse(a+k+1,a+n+1);    //逆序
    for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
} 

//前缀和
//s[i]表示 a[1]+a[2]...a[i]的和
//a[l]+a[l+1]...a[r]=s[r]-s[l-1] 
for(int i=1;i<=n;i++)
{
    cin>>a[i];
    s[i]=s[i-1]+a[i];
}
while(m--)
{
    cin>>l>>r;
    cout<<s[r]-s[l-1]<<endl;
} 

//差分
//b[i] 表示a[i]-a[i-1]的差值
//a的l到r这段增加等价于 b[l]+=c,b[r+1]-=c; 

for(int i=1;i<=n;i++)
{
    scanf("%d",&a[i]);
    b[i]=a[i]-a[i-1];
}
while(m--)
{
    int l,r,c;
    scanf("%d%d%d",&l,&r,&c);
    b[l]+=c;
    b[r+1]-=c;
}
for(int i=1;i<=n;i++)
{
    a[i]=a[i-1]+b[i];
} 

//组合计数
//递推计算c[a][b] (c[i][j]表示在i个不同的数中选择j个不同的数的方案数目)
for(int i=0;i<N;i++)
{
    for(int j=0;j<=i;j++)
    {
        if(j==0) c[i][j]=1;
        else c[i][j]=(c[i-1][j-1]+c[i-1][j])%P;
        //             选         不选 
    }
} 

//第一类斯特林数(s[n][k]表示将n个不同的数组成k个圆排列的方案数 )
s[0][0]=1;
for(int i=1;i<=n;i++)
{
	for(int j=1;j<=i;j++)
	{
		s[i][j]=s[i-1][j-1]+(i-1)*s[i-1][j];
		//       第i个数自己一个盘子  第i个数放到前面的j个盘子里面 
		s[i][j]%=P;
	}
} 

////第二类斯特林数(s[i][j]表示i个不同的元素放到j个集合的方案数 )
s[0][0]=1;
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=i;j++)
    {
        s[i][j]=s[i-1][j-1]+j*s[i-1][j];
        //      第i个独立   i选一个集合放
        s[i][j]%=P;
    }
}

卡特兰数 
//卡特兰数的第一种递推公式 c[2*n][n]/(n+1) 
// 卡特兰的第二种递归公式  f[n]=f[0]*f[n-1]+f[1]*f[n-2]....f[n-1]*f[0]

常见的应用:
https://blog.csdn.net/cz9797/article/details/105366774/