我的ACM算法模板
1ACM 模板王克纯王克纯 2018 年年 4 月月 19 日日2一些常量和函数：一些常量和函数： 最大 Long long _int64 INF = (_int64)0x1)string str;1. 字符串长度len = str.length();len = str.size();2. 字符串比较可以直接比较也可以:str1.compare(str2); str1.compare(pos1,len1,str2,pos2,len2); 值为负，0 ，正。nops 长度到完。 3. 附加str1 += str2;或str1.append(str2);str1.append(str2.pos2,len2);4. 字符串提取str2 = str1.substr();str2 = str1.substr(pos1);str2 = str1.substr(pos1,len1);5. 字符串搜索where = str1.find(str2);where = str1.find(str2,pos1); pos1 是从 str1 的第几位开始。where = str1.rfind(str2); 从后往前搜。 6. 插入字符串不是赋值语句。str1.insert(pos1,str2);str1.insert(pos1,str2,pos2,len2);str1.insert(pos1,numchar,char); numchar 是插入次数，char 是要插入 的字符。7. 替换字符串str1.replace(pos1,str2);str1.replace(pos1,str2,pos2,len2);8. 删除字符串str.erase(pos,len)str.clear();9. 交换字符串swap(str1,str2);10. C C+char *cstr = “Hello“;string str1;cstr = cstr;string str2(cstr);数学相关：数学相关： PICK 的定理的定理：三角形面积 s 三角形内部点 n 三角形边上的点 w n + w/2 - 1 = s欧几里德欧几里德辗转辗转相除法相除法 gcd(a, b) = gcd(b, a mod b) int gcd(int a, int b)int temp;while (b != 0)temp = b;b = a % b;a = temp;return a;PS: 最小公倍数 = a * b / gcd(a, b)扩扩展欧几里得展欧几里得 方程方程 ax + by = C 的（的（x）最小正整数解）最小正整数解#include #include int x,y,a,b; int extended_gcd(int a, int b)if (b = 0)x = 1; y = 0;return a;elseint r = extended_gcd(b, a % b);int temp;temp = x;x = y;y = temp - a / b * y;return r;int main()int i,j,m,s,c;scanf(“%d%d%d“, m = extended_gcd(a,b);if (c%m!=0) printf(“error“); return 0;x = x*(c/m);s = b/m;x = (x%s + s)%s;y = (c-x*a)/b;printf(“%d %dn“, x,y);printf(“gcd = %dn“, m);system(“pause“);素数素数筛筛子子 a = 0 为素数#include #include #include #define MAX 10000int aMAX;void odd()int i,j;memset(a,0,sizeof(a);for (i=2;i#include #include _int64 exgcd(_int64 a,_int64 b,_int64 return a;_int64 r=exgcd(b,a%b,x,y);_int64 t=x;x=y;y=t-a/b*y;return r;int main()_int64 flag=1,ans,x,y;/flag 是否有解，ans 存解得值 int num;/num 方程数目scanf(“%d“, num-; _int64 a,r;scanf(“%I64d“,/a 第一个除数scanf(“%I64d“, /r 第一个余数 while(num-)_int64 b,_r;scanf(“%I64d“,/b 除数 scanf(“%I64d“,/_r 余数 _int64 t=_r-r;_int64 d=exgcd(a,b,x,y);if(t%d) flag=0;_int64 temp=b/d;x*=t/d;x=(x%temp+temp)%temp;_int64 lcm=a*b/d;ans=a*x+r;ans=(ans%lcm+lcm)%lcm;a=lcm,r=ans;if (flag) printf(“%I64dn“,ans);else printf(“No answern“);/system(“pause“);求解模求解模线线性方程性方程组组(中国余数定理中国余数定理) /b0,b1,b2.必须互质 int ext_gcd(int a,int b,intif (!b)x=1,y=0;return a;ret=ext_gcd(b,a%b,x,y);t=x,x=y,y=t-a/b*y;return ret;/ x = b0 (mod w0)/ x = b1 (mod w1)/ ./ x = bk-1 (mod wk-1)/要求 wi>0,wi与 wj互质,解的范围 1.n,n=w0*w1*.*wk-1 int modular_linear_system(int b,int w,int k)int d,x,y,a=0,m,n=1,i;for (i=0;i#include #include using namespace std;const int MAX = 4000000;int total;int n,k;int farey2MAX;void make_farey_seq(int x1,int y1,int x2, int y2) if(x1+x2 > n | y1+y2 > n) return;make_farey_seq(x1, y1,x1+x2, y1+y2);total +;farey0total = x1+x2;farey1total = y1+y2;make_farey_seq(x1+x2, y1+y2,x2,y2);3int main()int t;total = 1;farey01 = 0;farey11 = 1;n = 4;/n 表示阶数make_farey_seq(0,1,1,1);farey0total+1 = 1;farey1total+1 = 1;while (1)scanf(“%d“,printf(“%d/%dn“,farey0t,farey1t);欧拉函数欧拉函数int gcd(int a,int b)return b?gcd(b,a%b):a;inline int lcm(int a,int b)return a/gcd(a,b)*b;/求 1.n-1 中与 n 互质的数的个数 int eular(int n)int ret=1,i;for (i=2;i*i1)ret*=n-1;return ret;费马费马小定理小定理 费马小定理 设 a 是正整数，p 是素数，且 a 和 p 互素 则 ap-1 1 (mod p) 欧拉定理欧拉定理 a 和 n 都是正整数，且 a 和 n 互素 a(n) 1 (mod n) 幂幂模模 ab (mod n) = a(b % (n) + (n) (mod n)n 是任意正整数，a 和 b 是任意整数，且 b 不小于 (n) 多多项项式求根式求根(牛牛顿顿法法)/* 牛顿法解多项式的根输入：多项式系数 c，多项式度数 n，求在a,b间的根输出：根要求保证a,b间有根 */double fabs( double x )return (x0; i-)p = p*x + ci-1;return p;int newton(double x0, double *r, double c, double cp, int n, double a, double b, double eps)int MAX_ITERATION = 1000;int i = 1;double x1, x2, fp, eps2 = eps/10.0;x1 = x0;while (i 1.0)return 0;x2 = x1 - x2/fp;if (fabs(x1-x2)b)return 0;*r = x2;return 1;x1 = x2;i+;return 0;double Polynomial_Root(double c, int n, double a, double b, double eps)double *cp;int i;double root;cp = (double *)calloc(n, sizeof(double);for (i=n-1; i>=0; i-) cpi = (i+1)*ci+1;if (a>b) root = a; a = b; b = root;if (!newton(a, free(cp);if (fabs(root)#include #include int main()int i,k1,j,t;int a4 = 1,2,8,10,ans16;memset(ans,0,sizeof(ans);k1 = 4;t = 0;for(i=0;i1)test = n%2;if(test=0)multi(b,b,b);n = n/2;elsemulti(c,b,c);n = n-1;multi(c,b,c);调用 ppow(b,n,c); b 矩阵的 n 次幂 初始化 b 为原矩阵 c 为单位矩阵结果保存在 c 中，每次使用都要初始化 b 和 c矩矩阵阵加速加速带带 mod #define p 2#define q 2#define mod 10000_int64 c22,n;_int64 a22 = 1,1,1,0;void init(_int64 cq)int i,j;for (i=0;i1)test = n%2;if(test=0)multi(b,b,b);n = n/2;elsemulti(c,b,c);n = n-1;multi(c,b,c);/矩阵中的数=mod 不为 0 故最后矩阵所有数要%mod矩矩阵阵快速快速幂幂（ （结结构体构体实现实现） ） 并求并求连续连续矩矩阵阵和和 #includetypedef struct nodeint matrix3232;Matrix;Matrix data,unit;int n,k,m;Matrix add(Matrix a,Matrix b)Matrix c;int i,j;for(i=0;i>=1;q=mul(q,q);p=mul(p,q);return p;Mat
