个人整理 ACM 模板.docx

头文件
#define_CRT_SBCURE_NO_DEPRECATE
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>

usingnamespacestd;

constintmaxn=110;
constintINF=0x3f3f3f3f;

经典
1.埃拉托斯特尼筛法
/*
|埃式筛法|
|快速筛选素数|
|16/11/05ztx|
*/

intprime[maxn];
boolis_prime[maxn];

intsieve(intn){
intp=0;
for(inti=0;i<=n;++i)
is_prime[i]=true;
is_prime[0]=is_prime[1]=false;
for(inti=2;i<=n;++i){//注意数组大小是n
if(is_prime[i]){
prime[p++]=i;
for(intj=i+i;j<=n;j+=i)//轻剪枝，j必定是i的倍数
is_prime[j]=false;
}
}
returnp;//返回素数个数
}

2.快速幂
/*
|快速幂|
|16/11/05ztx|
*/

typedeflonglongLL;//视数据大小的情况而定

LLpowerMod(LLx,LLn,LLm)
{
LLres=1;
while(n>0){
if(n&1)//判断是否为奇数，若是则true
res=(res*x)%m;
x=(x*x)%m;
n>>=1;//相当于n/=2;
}
returnres;
}

3.大数模拟
大数加法
/*
|大数模拟加法|
|用string模拟|
|16/11/05ztx,thankstocaojiji|
*/

stringadd1(strings1,strings2)
{
if(s1==""&&s2=="")return"0";
if(s1=="")returns2;
if(s2=="")returns1;
stringmaxx=s1,minn=s2;
if(s1.length()<s2.length()){
maxx=s2;
minn=s1;
}
inta=maxx.length()-1,b=minn.length()-1;
for(inti=b;i>=0;--i){
maxx[a--]+=minn[i]-'0';//a一直在减，额外还要减个'0'
}
for(inti=maxx.length()-1;i>0;--i){
if(maxx[i]>'9'){
maxx[i]-=10;//注意这个是减10
maxx[i-1]++;
}
}
if(maxx[0]>'9'){
maxx[0]-=10;
maxx='1'+maxx;
}
returnmaxx;
}

大数阶乘
/*
|大数模拟阶乘|
|用数组模拟|
|16/12/02ztx|
*/

#include<iostream>
#include<cstdio>

usingnamespacestd;

typedeflonglongLL;

constintmaxn=100010;

intnum[maxn],len;

/*
在mult函数中，形参部分：len每次调用函数都会发生改变，n表示每次要乘以的数，最终返回的是结果的长度
tip:阶乘都是先求之前的(n-1)!来求n!
初始化Init函数很重要，不要落下
*/

voidInit(){
len=1;
num[0]=1;
}

intmult(intnum[],intlen,intn){
LLtmp=0;
for(LLi=0;i<len;++i){
tmp=tmp+num[i]*n;//从最低位开始，等号左边的tmp表示当前位，右边的tmp表示进位（之前进的位）
num[i]=tmp%10;//保存在对应的数组位置，即去掉进位后的一位数
tmp=tmp/10;//取整用于再次循环,与n和下一个位置的乘积相加
}
while(tmp){//之后的进位处理
num[len++]=tmp%10;
tmp=tmp/10;
}
returnlen;
}

intmain(){
Init();
intn;
n=1977;//求的阶乘数
for(inti=2;i<=n;++i){
len=mult(num,len,i);
}
for(inti=len-1;i>=0;--