1、枚举一个序列内所有区间（子序列）的模板
for(len=1;len<=n;len++)
1、枚举一个序列内所有区间（子序列）的模板
for(len=1;len<=n;len++)
{//外层循环枚举长度
for(int l=1;l+len-1<=n;l++)
{//内层循环枚举左边界
int r=l+len-1;//确定右边界
[l,r]//这样就枚举了一个区间,如果对这个区间操作可以在这里写代码
}
}
功能：暴力解决一维数组区间问题。比如求区间和，区间中位数等等。也是区间动态规划的一个重要模板
2、数位分离模板（for),while循环的模板就是对for循环的拆解。
for(int i=n;i>0;i=i/10)//注意：如果n的类型是long long型的，那么这里的int要改成long long
{
//循环体中对 i%10 进行操作 ，i%10就是n的各位上的数字
}
功能：求一个整数的各位上的数字，求反转的数字，判断回文数等等
3、桶的模板
限制：桶的大小不能超过10^8 不能小于0.即一维数组的大小
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a[x]++
}
主要功能：统计数组的整数的个数。可以用来排序，去重排序、统计名次，统计名次的数值（成绩）、一个整数序列中不同整数的个数等等。
4、最大公约数模板。一般函数的形式
int gcd(int a,int b)
{//返回a和b的最大公约数
if(a%b==0)return b;
else return gcd(b,a%b);
}
主要功能：快速求整数a和b的最大公约数
4、前缀和模板
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
主要功能：1、通过s数组可以快速求出任意区间[l,r]的和。2、累加和的使用。
5、差分模板
for(int i=1;i<=n;i++)
{
a[i]=s[i]-s[i-1];
}//求差分数组，特殊情况下，不用求，默认值位差分数组
while(q--)
{
int l,r;
cin>>l>>r;
a[l]+=c;
a[r+1]-=c;
}//在q个区间操作，区间内的每个数同时加c.(c可以是负数）
for(int i=1;i<=n;i++)
{
s[i]=s[i-1]+a[i];
}
//再求一次前缀和
主要功能：快速的对任意区间进行同样的操作。 缺点：只能最后查询，不能边操作边查询
6、二分枚举模板
bool check(int x)
{//根据具体问题，统计二分的返回值。
}
int l=mn,r=mx+1;//先确定枚举范围
while(l<r)
{
int mid=(l+r)/2;
if(check(mid))
{
l=mid+1;//或者 r=mid;
}
else
{
r=mid;//或者 l=mid+1;
}
}
//如果求最大值 输出l-1 求最小值输出l
cout<<l;//或者l-1
主要功能：把o(n)的顺序枚举变成o(logn)的枚举。前提条件：二分的值必须具有单调性。
6、倍增（快速幂）
求：a^b%p的值
int qmi(int a,int b)
{
int res=1;//b==0时，默认a^0==1
while(b)//b==0时退出
{
if(b&1)res=res*a%p;
a=a*a%p;//倍增 如果a*a的结果可能超过int ,则a的类型应该定义位long long
b>>=1;//b右移1位
}
return res;
}
主要功能：使用倍增算法，快速求出a^b%p的值。
7、唯一分解定理
int n;
cin>>n;
for(i=2;i<=n/i;i++)
{
if(n%i==0)
{
int cnt=0;
while(n%i==0)
{
cnt++;
n=n/i;
}
cout<<i<<" "<<cnt<<endl;//在这里可以对质因数及质因数的个数进行操作
}
}
if(n>1)cout<<n<<" "<<1<<endl;//最后别忘记有可能还有一个大于sqrt(n)的质因数
主要功能：求整数n的质因数及对应的个数。
相关定理： 设：n=p1^a1 * p2^a2 * p3^a3 * .... *pk^ak
其中：p1,p2....pk是n的质因数。 a1 a2 a3...ak是对应的个数则
n的因数的个数=（a1+1)*(a2+1)*....*(ak+1)
n的所有的因数之和=（p1^0+p1+p1^2+...p1^a1)*(p2^0+p2+p2^2+...p2^ak)*...*(pk^0+pk+pk^2+..+pk^ak)
{//外层循环枚举长度
for(int l=1;l+len-1<=n;l++)
{//内层循环枚举左边界
int r=l+len-1;//确定右边界
[l,r]//这样就枚举了一个区间,如果对这个区间操作可以在这里写代码
}
}
功能：暴力解决一维数组区间问题。比如求区间和，区间中位数等等。也是区间动态规划的一个重要模板
2、数位分离模板（for),while循环的模板就是对for循环的拆解。
for(int i=n;i>0;i=i/10)//注意：如果n的类型是long long型的，那么这里的int要改成long long
{
//循环体中对 i%10 进行操作 ，i%10就是n的各位上的数字
}
功能：求一个整数的各位上的数字，求反转的数字，判断回文数等等
3、桶的模板
限制：桶的大小不能超过10^8 不能小于0.即一维数组的大小
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a[x]++
}
主要功能：统计数组的整数的个数。可以用来排序，去重排序、统计名次，统计名次的数值（成绩）、一个整数序列中不同整数的个数等等。
4、最大公约数模板。一般函数的形式
int gcd(int a,int b)
{//返回a和b的最大公约数
if(a%b==0)return b;
else return gcd(b,a%b);
}
主要功能：快速求整数a和b的最大公约数
4、前缀和模板
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
}
主要功能：1、通过s数组可以快速求出任意区间[l,r]的和。2、累加和的使用。
5、差分模板
for(int i=1;i<=n;i++)
{
a[i]=s[i]-s[i-1];
}//求差分数组，特殊情况下，不用求，默认值位差分数组
while(q--)
{
int l,r;
cin>>l>>r;
a[l]+=c;
a[r+1]-=c;
}//在q个区间操作，区间内的每个数同时加c.(c可以是负数）
for(int i=1;i<=n;i++)
{
s[i]=s[i-1]+a[i];
}
//再求一次前缀和
主要功能：快速的对任意区间进行同样的操作。 缺点：只能最后查询，不能边操作边查询
6、二分枚举模板
bool check(int x)
{//根据具体问题，统计二分的返回值。
}
int l=mn,r=mx+1;//先确定枚举范围
while(l<r)
{
int mid=(l+r)/2;
if(check(mid))
{
l=mid+1;//或者 r=mid;
}
else
{
r=mid;//或者 l=mid+1;
}
}
//如果求最大值 输出l-1 求最小值输出l
cout<<l;//或者l-1
主要功能：把o(n)的顺序枚举变成o(logn)的枚举。前提条件：二分的值必须具有单调性。
6、倍增（快速幂）
求：a^b%p的值
int qmi(int a,int b)
{
int res=1;//b==0时，默认a^0==1
while(b)//b==0时退出
{
if(b&1)res=res*a%p;
a=a*a%p;//倍增 如果a*a的结果可能超过int ,则a的类型应该定义位long long
b>>=1;//b右移1位
}
return res;
}
主要功能：使用倍增算法，快速求出a^b%p的值。
7、唯一分解定理
int n;
cin>>n;
for(i=2;i<=n/i;i++)
{
if(n%i==0)
{
int cnt=0;
while(n%i==0)
{
cnt++;
n=n/i;
}
cout<<i<<" "<<cnt<<endl;//在这里可以对质因数及质因数的个数进行操作
}
}
if(n>1)cout<<n<<" "<<1<<endl;//最后别忘记有可能还有一个大于sqrt(n)的质因数
主要功能：求整数n的质因数及对应的个数。
相关定理： 设：n=p1^a1 * p2^a2 * p3^a3 * .... *pk^ak
其中：p1,p2....pk是n的质因数。 a1 a2 a3...ak是对应的个数则
n的因数的个数=（a1+1)*(a2+1)*....*(ak+1)
n的所有的因数之和=（p1^0+p1+p1^2+...p1^a1)*(p2^0+p2+p2^2+...p2^ak)*...*(pk^0+pk+pk^2+..+pk^ak)