个人整理 ACM 模板.doc

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

1、.0.头文件#define_CRT_SBCURE_NO_DEPRECATE#include#include#include#include#include#include#include#include#include#include#include#includeusingnamespacestd;constintmaxn=110;1.constintINF=0x3

2、f3f3f3f;经典1.埃拉托斯特尼筛法/*word范文.

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_prime[i]){prime[p++]=i;for(intj=i+i;j<=n;j+=i)//轻剪枝，j必定是i的倍数is_prime

9、[j]=false;}}returnp;//返回素数个数word范文.}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;//相当于n/=2;}returnres;}word范文.3.大数模拟大数加法/*

14、大数模拟加法

15、

16、用string模拟

17、

18、16/11/05ztx,thankstocaojiji

19、*/strin

20、gadd1(strings1,strings2){if(s1==""&&s2=="")return"0";if(s1=="")returns2;if(s2=="")returns1;stringmaxx=s1,minn=s2;if(s1.length()=0;--i){maxx[a--]+=minn[i]-'0';//a一直在减，额外还要减个'0'word范文.}for(inti=maxx.length

21、()-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、16/12/02ztx

27、*/word范文.#include#includeusingnamespacestd;typedeflonglongLL;constintmaxn=100010;intnum[maxn],len;/*在mult函数中，形参部分

28、：len每次调用函数都会发生改变，n表示每次要乘以的数，最终返回的是结果的长度tip:阶乘都是先求之前的(n-1)!来求n!初始化Init函数很重要，不要落下*/voidInit(){len=1;num[0]=1;}word范文.intmult(intnum[],intlen,intn){LLtmp=0;for(LLi=0;i

29、次循环,与n和下一个位置的乘积相加}while(tmp){//之后的进位处理num[len++]=tmp%10;tmp=tmp/10;}returnlen;}intmain(){Init();intn;n=1977;//求的阶乘数word范文.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/*

30、辗转相除法

31、

32、欧几里得算法

33、

34、求最大公约