个人整理-ACM-模板.docx

《个人整理-ACM-模板.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、0.头文件#define_CRT_SBCURE_NO_DEPRECATE#include#include#include#include#include#include#include#include#include#include#include#includeusingnamespacestd

2、;constintmaxn=110;1.constintINF=0x3f3f3f3f;经典1.埃拉托斯特尼筛法/*

3、埃式筛法

4、

5、快速筛选素数

6、

7、16/11/05ztx

8、*/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){//注意数组大小是nif(is_prim

9、e[i]){prime[p++]=i;for(intj=i+i;j<=n;j+=i)//轻剪枝，j必定是i的倍数is_prime[j]=false;}}returnp;//返回素数个数}2.快速幂/*

10、快速幂

11、

12、16/11/05ztx

13、*/typedeflonglongLL;//视数据大小的情况而定LLpowerMod(LLx,LLn,LLm){LLres=1;while(n>0){if(n&1)//判断是否为奇数，若是则trueres=(res*x)%m;x=(x*x)%m;n>>=1;//相

14、当于n/=2;}returnres;}3.大数模拟大数加法/*

15、大数模拟加法

16、

17、用string模拟

18、

19、16/11/05ztx,thankstocaojiji

20、*/stringadd1(strings1,strings2){if(s1==""&&s2=="")return"0";if(s1=="")returns2;if(s2=="")returns1;stringmaxx=s1,minn=s2;if(s1.length()

21、axx.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;//注意这个是减10maxx[i-1]++;}}if(maxx[0]>'9'){maxx[0]-=10;maxx='1'+maxx;}returnmaxx;}大数阶乘/*

22、大数模拟阶乘

23、

24、

25、用数组模拟

26、

27、16/12/02ztx

28、*/#include#includeusingnamespacestd;typedeflonglongLL;constintmaxn=100010;intnum[maxn],len;/*在mult函数中，形参部分：len每次调用函数都会发生改变，n表示每次要乘以的数，最终返回的是结果的长度tip:阶乘都是先求之前的(n-1)!来求n!初始化Init函数很重要，不要落下*/voidInit(){len=1;num[0]=1

29、;}intmult(intnum[],intlen,intn){LLtmp=0;for(LLi=0;i

30、;}intmain(){Init();intn;n=1977;//求的阶乘数for(inti=2;i<=n;++i){len=mult(num,len,i);}for(inti=len-1;i>=0;--i)printf("%d",num[i]);//从最高位依次输出,数据比较多采用printf输出printf("");return0;}4.GCD/*

31、辗转相除法

32、

33、欧几里得算法

34、

35、求最大公约数

36、

37、16/11/05ztx

38、*/intgcd(intbig,intsmall){if(small>