ACM函数整理_ACM模板

三角形面积计算 (1)字典树模板 (2)求线段所在直线 (5)求外接圆 (5)求内接圆 (6)判断点是否在直线上 (8)简单多边形面积计算公式 (8)stein算法求最大共约数 (9)最长递增子序列模板——o(nlogn算法实现) (9)判断图中同一直线的点的最大数量 (10)公因数和公倍数 (12)已知先序中序求后序 (12)深度优先搜索模板 (13)匈牙利算法——二部图匹配BFS实现 (15)带输出路径的prime算法 (17)prime模板 (18)kruskal模板 (19)dijsktra (22)并查集模板 (23)高精度模板 (24)三角形面积计算//已知三条边和外接圆半径，公式为s = a*b*c/(4*R)double GetArea(double a, double b, double c, double R){return a*b*c/4/R;}//已知三条边和内接圆半径，公式为s = prdouble GetArea(double a, double b, double c, double r){return r*(a+b+c)/2;}//已知三角形三条边，求面积double GetArea(doule a, double b, double c){double p = (a+b+c)/2;return sqrt(p*(p-a)*(p-b)*(p-c));}//已知道三角形三个顶点的坐标struct Point{double x, y;Point(double a = 0, double b = 0){x = a; y = b;}};double GetArea(Point p1, Point p2, Point p3){double t =-p2.x*p1.y+p3.x*p1.y+p1.x*p2.y-p3.x*p2.y-p1.x*p3.y+p2.x*p3.y;if(t < 0) t = -t;return t/2;}字典树模板#include <stdio.h>#include <string.h>#include <memory.h>#define BASE_LETTER 'a'#define MAX_TREE 35000#define MAX_BRANCH 26struct{int next[MAX_BRANCH]; //记录分支的位置int c[MAX_BRANCH]; //查看分支的个数int flag; //是否存在以该结点为终止结点的东东，可以更改为任意的属性}trie[MAX_TREE];int now;void init(){now = 0;memset(&trie[now], 0, sizeof(trie[now]));now ++;}int add (){memset(&trie[now], 0, sizeof(trie[now]));return now++;}int insert( char *str){int pre = 0, addr;while( *str != 0 ){addr = *str - BASE_LETTER;if( !trie[pre].next[addr] )trie[pre].next[addr] = add();trie[pre].c[addr]++;pre = trie[pre].next[addr];str ++;}trie[pre].flag = 1;return pre;}int search( char *str ){int pre = 0, addr;while( *str != 0 ){addr = *str - BASE_LETTER;if ( !trie[pre].next[addr] )return 0;pre = trie[pre].next[addr];str ++;}if( !trie[pre].flag )return 0;return pre;}pku2001题，源代码：void check( char *str ){int pre = 0, addr;while(*str != 0){addr = *str - BASE_LETTER;if( trie[pre].c[addr] == 1) {printf("%c\n", *str);return;}printf("%c", *str);pre = trie[pre].next[addr];str ++;}printf("\n");}char input[1001][25];int main(){int i = 0,j;init();while(scanf("%s", input[i]) != EOF){getchar();insert(input[i]);i++;}for(j = 0; j < i; j ++){printf("%s ", input[j]);check(input[j]);}return 0;}求线段所在直线//*****************************线段所在的直线struct Line{double a, b, c;};struct Point{double x, y;}Line GetLine(Point p1, Point p2){//ax+by+c = 0返回直线的参数Line line;line.a = p2.y - p1.y;line.b = p1.x - p2.x;line.c = p2.x*p1.y - p1.x*p2.y;return line;}求外接圆//***************已知三角形三个顶点坐标，求外接圆的半径和坐标********************struct Point{double x, y;Point(double a = 0, double b = 0){x = a; y = b;}};struct TCircle{double r;Point p;}double distance(Point p1, Point p2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}double GetArea(doule a, double b, double c){double p = (a+b+c)/2;return sqrt(p*(p-a)*(p-b)*(p-c));}TCircle GetTCircle(Point p1, Point p2, Point p3){double a, b, c;double xa,ya, xb, yb, xc, yc, c1, c2;TCircle tc;a = distance(p1, p2);b = distance(p2, p3);c = distance(p3, p1);//求半径tc.r = a*b*c/4/GetArea(a, b, c);//求坐标xa = p1.x; ya = p1.b;xb = p2.x; yb = p2.b;xc = p3.x; yc = p3.b;c1 = (xa*xa + ya*ya - xb*xb - yb*yb)/2;c2 = (xa*xa + ya*ya - xc*xc - yc*yc)/2;tc.p.x = (c1*(ya-yc) - c2*(ya-yb))/((xa-xb)*(ya-yc) - (xa-xc)*(ya-yb)); tc.p.y = (c1*(xa-xc) - c2*(xa-xb))/((ya-yb)*(xa-xc) - (ya-yc)*(xa-xb));return tc;}求内接圆struct Point{double x, y;Point(double a = 0, double b = 0){x = a; y = b;}};struct TCircle{double r;Point p;}double distance(Point p1, Point p2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}double GetArea(doule a, double b, double c){double p = (a+b+c)/2;return sqrt(p*(p-a)*(p-b)*(p-c));}TCircle GetTCircle(Point p1, Point p2, Point p3){double a, b, c;double xa,ya, xb, yb, xc, yc, c1, c2, f1, f2;double A,B,C;TCircle tc;a = distance(p1, p2);b = distance(p3, p2);c = distance(p3, p1);//求半径tc.r = 2*GetArea(a, b, c)/(a+b+c);//求坐标A = acos((b*b+c*c-a*a)/(2*b*c));B = acos((a*a+c*c-b*b)/(2*a*c));C = acos((a*a+b*b-c*c)/(2*a*b));p = sin(A/2); p2 = sin(B/2); p3 = sin(C/2);xb = p1.x; yb = p1.b;xc = p2.x; yc = p2.b;xa = p3.x; ya = p3.b;f1 = ( (tc.r/p2)*(tc.r/p2) - (tc.r/p)*(tc.r/p) + xa*xa - xb*xb + ya*ya - yb*yb)/2;f2 = ( (tc.r/p3)*(tc.r/p3) - (tc.r/p)*(tc.r/p) + xa*xa - xc*xc + ya*ya - yc*yc)/2;tc.p.x = (f1*(ya-yc) - f2*(ya-yb))/((xa-xb)*(ya-yc)-(xa-xc)*(ya-yb)); tc.p.y = (f1*(xa-xc) - f2*(xa-xb))/((ya-yb)*(xa-xc)-(ya-yc)*(xa-xb));return tc;}判断点是否在直线上//**************判断点是否在直线上********************* //判断点p是否在直线[p1,p2]struct Point{double x,y;};bool isPointOnSegment(Point p1, Point p2, Point p0){//叉积是否为0，判断是否在同一直线上if((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y) != 0)return false;//判断是否在线段上if((p0.x > p1.x && p0.x > p2.x) || (p0.x < p1.x && p0.x < p2.x)) return false;if((p0.y > p1.y && p0.y > p1.y) || (p0.y < p1.y && p0.y < p2.y)) return false;return true;}简单多边形面积计算公式struct Point{double x, y;Point(double a = 0, double b = 0){x = a; y = b;}};Point pp[10];double GetArea(Point *pp, int n){//n为点的个数，pp中记录的是点的坐标int i = 1;double t = 0;for(; i <= n-1; i++)t += pp[i-1].x*pp[i].y - pp[i].x*pp[i-1].y;t += pp[n-1].x*pp[0].y - pp[0].x*pp[n-1].y;if(t < 0) t = -t;return t/2;}stein算法求最大共约数int gcd(int a,int b){if (a == 0) return b;if (b == 0) return a;if (a % 2 == 0 && b % 2 == 0) return 2 * gcd(a/2,b/2); else if (a % 2 == 0) return gcd(a/2,b);else if (b % 2 == 0) return gcd(a,b/2);else return gcd(abs(a-b),min(a,b));}最长递增子序列模板——o(nlogn算法实现)#include <stdio.h>#define MAX 40000int array[MAX], B[MAX];int main(){int count,i,n,left,mid,right,Blen=0,num;scanf("%d",&count); //case的个数while(count--){scanf("%d",&n); //每组成员的数量Blen = 0;for(i=1;i<=n;i++)scanf("%d",&array[i]); //读入每个成员for(i=1;i<=n;i++){num = array[i];left = 1;right = Blen;while(left<=right){mid = (left+right)/2;if(B[mid]<num)left = mid+1;elseright = mid-1;}B[left] = num;if(Blen<left)Blen++;}printf("%d\n",Blen);//输出结果}return 1;}判断图中同一直线的点的最大数量#include <iostream>#include <cstdio>#include <memory>using namespace std;#define MAX 1010 //最大点的个数struct point{int x,y;}num[MAX];int used[MAX][MAX*2]; //条件中点的左边不会大于1000,just equal MAX int countN[MAX][MAX*2];#define abs(a) (a>0?a:(-a))int GCD(int x, int y){int temp;if(x < y){temp = x; x = y; y = temp;}while(y != 0){temp = y;y = x % y;x = temp;}return x;}int main(){int n,i,j;int a,b,d,ans;while(scanf("%d", &n)==1){//initeans = 1;memset(used, 0, sizeof(used));memset(countN, 0, sizeof(countN));//readfor(i = 0; i < n; i++)scanf("%d%d", &num[i].x, &num[i].y);for(i = 0; i < n-1; i++){for(j = i+1; j < n; j++){b = num[j].y-num[i].y;a = num[j].x-num[i].x;if(a < 0) //这样可以让（2，3）（－2，－3）等价{a = -a; b = -b;}d = GCD(a,abs(b));a /= d;b /= d; b += 1000;//条件中点的左边不会大于1000if(used[a][b] != i+1){used[a][b] = i+1;countN[a][b] = 1;}else{countN[a][b]++;if(ans < countN[a][b])ans = countN[a][b];}}//for}//forprintf("%d\n", ans+1);}return 0;}公因数和公倍数int GCD(int x, int y){int temp;if(x < y){temp = x; x = y; y = temp;}while(y != 0){temp = y;y = x % y;x = temp;}return x;}int beishu(int x, int y){return x * y / GCD(x,y);}已知先序中序求后序#include <iostream>#include <string>using namespace std;string post;void fun(string pre, string mid){if(pre == "" || mid == "") return;int i = mid.find(pre[0]);fun(pre.substr(1,i), mid.substr(0,i));fun(pre.substr(i+1, (int)pre.length()-i-1), mid.substr(i+1, (int)mid.length()-i-1));post += pre[0];}int main(){string pre, mid;while(cin >> pre){cin >> mid;post.erase();fun(pre, mid);cout << post << endl;}return 0;}深度优先搜索模板int t; //t用来标识要搜索的元素int count; //count用来标识搜索元素的个数int data[m][n]; //data用来存储数据的数组//注意，数组默认是按照1……n存储，即没有第0行//下面是4个方向的搜索,void search(int x, int y){data[x][y] = *; //搜索过进行标记if(x-1 >= 1 && data[x-1][y] == t){count++;search(x-1,y);}if(x+1 <= n && data[x+1][y] == t){count++;search(x+1,y);}if(y-1 >= 1 && data[x][y-1] == t){count++;search(x,y-1);}if(y+1 <= n && data[x][y+1] == t){count++;search(x,y+1);}}//下面是8个方向的搜索void search(int x, int y){data[x][y] = *; //搜索过进行标记if(x-1 >= 1){if(data[x-1][y] == t){count++;search(x-1,y);}if(y-1 >= 1 && data[x-1][y-1] == t) {count++;search(x-1,y-1);}if(y+1 <= n && data[x-1][y+1] == t) {count++;search(x-1,y+1);}}if(x+1 <= n){if(data[x+1][y] == t){count++;search(x+1,y);}if(y-1 >= 1 && data[x+1][y-1] == t) {count++;search(x+1,y-1);}if(y+1 <= n && data[x+1][y+1] == t) {count++;search(x+1,y+1);}}if(y-1 >= 1 && data[x][y-1] == t){count++;search(x,y-1);}if(y+1 <= n && data[x][y+1] == t){count++;search(x,y+1);}}匈牙利算法——二部图匹配BFS实现//匈牙利算法实现#define MAX 310 //二部图一侧顶点的最大个数int n,m; //二分图的两个集合分别含有n和m个元素。

ACM模板[王克纯2020年9月21日最大子串int maxSum(int * a,int n){int sum = a[0],b = 0;for(int i=0;i<n;++i){if(b>0) b += a[i];else b = a[i];if(b > sum) sum = b;}return sum;}int Kadane(const int array[], size_t length, unsigned int& left, unsigned int& right){unsigned int i, cur_left, cur_right;int cur_max, max;cur_max = max = left = right = cur_left = cur_right = 0;for(i = 0; i < length; ++i){cur_max += array[i];if(cur_max > 0){cur_right = i;if(max < cur_max){max = cur_max;left = cur_left;right = cur_right;}}else{cur_max = 0;cur_left = cur_right = i + 1;}}return max;} 快速幂void js(int &a,int &b,int num) {b=1;while(num){if(num&1) b*=a;num>>=1;a*=a;}}矩阵乘法struct mat{int n,m;//n行m列int data[MAX][MAX];};void mul(const mat& a,const mat& b,mat& c) //c=a*b{int i,j,k;if (a.m!=b.n); //报错c.n=a.n,c.m=b.m;for (i=0;i<c.n;i++){for (j=0;j<c.m;j++){for (c.data[i][j]=k=0;k<a.m;k++) {c.data[i][j]+=a.data[i][k]*b.dat a[k][j]%m;//m为余数}c.data[i][j]%=m;}}}Bit位操作(宏定义,内联函数,stl)} #define bitwrite(a,i,n)(n)?(a)[(i)/8]|=1<<(i)%8:(a)[(i)/8]&=~(1<<(i)%8)//数组a的第i位写入n;#define bitread(a,i)((a)[(i)/8]>>((i)%8))&1//读取数组a的第i位inline void write(int i,int n){n?a[i/8]|=1<<i%8:a[i/8]&=~(1<<i% 8);}inline int read(int i){return (a[i/8]>>(i%8))&1;}#include<bitset>bitset<MAX> b;错排公式为M(n)=n！（1/2!-1/3!+…..+(-1）^n/n!)M(n)=n!-n!/1!+n!/2!-n!/3!+…+(-1）^n*n!/n!=sigma(k=2~n) (-1）^k*n!/k!Dn=[n!/e+0.5]容斥原理M(n)=n![1/0!-1/1!+1/2!-1/3!+1/4! +..+(-1）^n/n!]二分模板LL findr(LL array, LL low, LL high,LL target){while(low <= high){LL mid = (low + high)/2;if (array[mid] > target) high = mid - 1;else if (array[mid] < target) low = mid + 1;else return mid;}return -1;复用代码#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX 10void print(mat t){printf("*****************\n") ;for(int i=0;i<t.n;i++){for(int j=0;j<t.m;j++){printf("%d",t.data[i][j]);}putchar('\n');}}一些常量和函数：最大Long long __int64 INF = ~(((__int64)0x1)<<63);ceil()向上取整(math.h)floor()向下取整c字符串处理函数1）提取子串--strstr函数原型：char* strstr(char*src,char*find)函数说明：从字符串src中寻找find第一次出现的位置（不比较结束符NULL）返回值：返回指向第一次出现find位置的指针，如果没有找到则返回NULL2）接尾连接--strcat函数原型：char* strcat(char*dest,char*src)函数说明：把src所指字符串添加到dest结尾处(覆盖dest结尾处的'\0')并添加'\0'3)部分连接--strncat函数原型:char* strncat(char*dest,char*src,int n);函数说明：把src所指字符串的前n个字符添加到dest结尾处（覆盖dest结尾处的’\0’）并添加’’\0’.返回值：返回指向dest的指针。

目录目录 (1)Graph 图论 (3)|DAG的深度优先搜索标记 (3)|无向图找桥 (3)|无向图连通度(割) (3)|最大团问题DP+DFS (3)|欧拉路径O(E) (3)|D IJKSTRA数组实现O（N^2） (3)|D IJKSTRA O(E* LOG E) (4)|B ELLMAN F ORD单源最短路O(VE) (4)|SPFA(S HORTEST P ATH F ASTER A LGORITHM) (4)|第K短路（D IJKSTRA） (5)|第K短路（A*） (5)|P RIM求MST (6)|次小生成树O(V^2) (6)|最小生成森林问题(K颗树)O(MLOGM) (6)|有向图最小树形图 (6)|M INIMAL S TEINER T REE (6)|T ARJAN强连通分量 (7)|弦图判断 (7)|弦图的PERFECT ELIMINATION点排列 (7)|稳定婚姻问题O(N^2) (7)|拓扑排序 (8)|无向图连通分支(DFS/BFS邻接阵) (8)|有向图强连通分支(DFS/BFS邻接阵)O(N^2) (8)|有向图最小点基(邻接阵)O(N^2) (9)|F LOYD求最小环 (9)|2-SAT问题 (9)Network 网络流 (11)|二分图匹配（匈牙利算法DFS实现） (11)|二分图匹配（匈牙利算法BFS实现） (11)|二分图匹配（H OPCROFT－C ARP的算法） (11)|二分图最佳匹配（KUHN MUNKRAS算法O(M*M*N)）..11 |无向图最小割O(N^3) (12)|有上下界的最小(最大)流 (12)|D INIC最大流O(V^2*E) (12)|HLPP最大流O(V^3) (13)|最小费用流O(V*E* F).......................................13|最小费用流O(V^2* F). (14)|最佳边割集 (15)|最佳点割集 (15)|最小边割集 (15)|最小点割集（点连通度） (16)|最小路径覆盖O(N^3) (16)|最小点集覆盖 (16)Structure 数据结构 (17)|求某天是星期几 (17)|左偏树合并复杂度O(LOG N) (17)|树状数组 (17)|二维树状数组 (17)|T RIE树(K叉) (17)|T RIE树(左儿子又兄弟) (18)|后缀数组O(N* LOG N) (18)|后缀数组O(N) (18)|RMQ离线算法O(N*LOG N)+O(1) (19)|RMQ(R ANGE M INIMUM/M AXIMUM Q UERY)-ST算法(O(NLOGN +Q)) (19)|RMQ离线算法O(N*LOG N)+O(1)求解LCA (19)|LCA离线算法O(E)+O(1) (20)|带权值的并查集 (20)|快速排序 (20)|2台机器工作调度 (20)|比较高效的大数 (20)|普通的大数运算 (21)|最长公共递增子序列O(N^2) (22)|0-1分数规划 (22)|最长有序子序列（递增/递减/非递增/非递减） (22)|最长公共子序列 (23)|最少找硬币问题（贪心策略-深搜实现） (23)|棋盘分割 (23)|汉诺塔 (23)|STL中的PRIORITY_QUEUE (24)|堆栈 (24)|区间最大频率 (24)|取第K个元素 (25)|归并排序求逆序数 (25)|逆序数推排列数 (25)|二分查找 (25)|二分查找（大于等于V的第一个值） (25)|所有数位相加 (25)Number 数论 (26)|递推求欧拉函数PHI(I) (26)|单独求欧拉函数PHI(X) (26)|GCD最大公约数 (26)|快速GCD (26)|扩展GCD (26)|模线性方程 A * X = B (% N) (26)|模线性方程组 (26)|筛素数[1..N] (26)|高效求小范围素数[1..N] (26)|随机素数测试(伪素数原理) (26)|组合数学相关 (26)|P OLYA计数 (27)|组合数C(N, R) (27)|最大1矩阵 (27)|约瑟夫环问题（数学方法） (27)|约瑟夫环问题（数组模拟） (27)|取石子游戏1 (27)|集合划分问题 (27)|大数平方根（字符串数组表示） (28)|大数取模的二进制方法 (28)|线性方程组A[][]X[]=B[] (28)|追赶法解周期性方程 (28)|阶乘最后非零位,复杂度O(NLOGN) (29)递归方法求解排列组合问题 (30)|类循环排列 (30)|全排列 (30)|不重复排列 (30)|全组合 (31)|不重复组合 (31)|应用 (31)模式串匹配问题总结 (32)|字符串H ASH (32)|KMP匹配算法O(M+N) (32)|K ARP-R ABIN字符串匹配 (32)|基于K ARP-R ABIN的字符块匹配 (32)|函数名: STRSTR (32)|BM算法的改进的算法S UNDAY A LGORITHM (32)|最短公共祖先（两个长字符串） (33)|最短公共祖先（多个短字符串）...............................33Geometry 计算几何.. (34)|G RAHAM求凸包O(N* LOG N) (34)|判断线段相交 (34)|求多边形重心 (34)|三角形几个重要的点 (34)|平面最近点对O(N* LOG N) (34)|L IUCTIC的计算几何库 (35)|求平面上两点之间的距离 (35)|(P1-P0)*(P2-P0)的叉积 (35)|确定两条线段是否相交 (35)|判断点P是否在线段L上 (35)|判断两个点是否相等 (35)|线段相交判断函数 (35)|判断点Q是否在多边形内 (35)|计算多边形的面积 (35)|解二次方程A X^2+B X+C=0 (36)|计算直线的一般式A X+B Y+C=0 (36)|点到直线距离 (36)|直线与圆的交点，已知直线与圆相交 (36)|点是否在射线的正向 (36)|射线与圆的第一个交点 (36)|求点P1关于直线LN的对称点P2 (36)|两直线夹角（弧度） (36)ACM/ICPC竞赛之STL (37)ACM/ICPC竞赛之STL简介 (37)ACM/ICPC竞赛之STL--PAIR (37)ACM/ICPC竞赛之STL--VECTOR (37)ACM/ICPC竞赛之STL--ITERATOR简介 (38)ACM/ICPC竞赛之STL--STRING (38)ACM/ICPC竞赛之STL--STACK/QUEUE (38)ACM/ICPC竞赛之STL--MAP (40)ACM/ICPC竞赛之STL--ALGORITHM (40)STL IN ACM (41)头文件 (42)线段树 (43)求矩形并的面积（线段树+离散化+扫描线） (43)求矩形并的周长（线段树+离散化+扫描线） (44)Graph 图论/*==================================================*\| DAG的深度优先搜索标记| INIT: edge[][]邻接矩阵; pre[], post[], tag全置0;| CALL: dfstag(i, n); pre/post:开始/结束时间\*==================================================*/int edge[V][V], pre[V], post[V], tag;void dfstag(int cur, int n){ // vertex: 0 ~ n-1pre[cur] = ++tag;for (int i=0; i<n; ++i) if (edge[cur][i]) {if (0 == pre[i]) {printf("Tree Edge!\n");dfstag(i,n);} else {if (0 == post[i]) printf("Back Edge!\n");else if (pre[i] > pre[cur])printf("Down Edge!\n");else printf("Cross Edge!\n");}}post[cur] = ++tag;}/*==================================================*\| 无向图找桥| INIT: edge[][]邻接矩阵;vis[],pre[],anc[],bridge 置0;| CALL: dfs(0, -1, 1, n);\*==================================================*/int bridge, edge[V][V], anc[V], pre[V], vis[V];void dfs(int cur, int father, int dep, int n){ // vertex: 0 ~ n-1if (bridge) return;vis[cur] = 1; pre[cur] = anc[cur] = dep;for (int i=0; i<n; ++i) if (edge[cur][i]) {if (i != father && 1 == vis[i]) {if (pre[i] < anc[cur])anc[cur] = pre[i];//back edge}if (0 == vis[i]) { //tree edgedfs(i,cur,dep+1,n);if (bridge) return;if (anc[i] < anc[cur]) anc[cur] = anc[i];if (anc[i] > pre[cur]) { bridge = 1; return; } }}vis[cur] = 2;}/*==================================================*\| 无向图连通度(割)| INIT: edge[][]邻接矩阵;vis[],pre[],anc[],deg[]置为0;| CALL: dfs(0, -1, 1, n);| k=deg[0], deg[i]+1(i=1…n-1)为删除该节点后得到的连通图个数| 注意:0作为根比较特殊!\*==================================================*/int edge[V][V], anc[V], pre[V], vis[V], deg[V];void dfs(int cur, int father, int dep, int n){// vertex: 0 ~ n-1int cnt = 0;vis[cur] = 1; pre[cur] = anc[cur] = dep;for (int i=0; i<n; ++i) if (edge[cur][i]) {if (i != father && 1 == vis[i]) {if (pre[i] < anc[cur])anc[cur] = pre[i];//back edge}if (0 == vis[i]) { //tree edgedfs(i,cur,dep+1,n);++cnt; // 分支个数if (anc[i] < anc[cur]) anc[cur] = anc[i];if ((cur==0 && cnt>1) ||(cnt!=0 && anc[i]>=pre[cur]))++deg[cur];// link degree of a vertex }}vis[cur] = 2;} /*==================================================*\| 最大团问题 DP + DFS| INIT: g[][]邻接矩阵;| CALL: res = clique(n);\*==================================================*/int g[V][V], dp[V], stk[V][V], mx;int dfs(int n, int ns, int dep){if (0 == ns) {if (dep > mx) mx = dep;return 1;}int i, j, k, p, cnt;for (i = 0; i < ns; i++) {k = stk[dep][i]; cnt = 0;if (dep + n - k <= mx) return 0;if (dep + dp[k] <= mx) return 0;for (j = i + 1; j < ns; j++) {p=stk[dep][j];if (g[k][p]) stk[dep + 1][cnt++] = p;}dfs(n, cnt, dep + 1);}return 1;}int clique(int n){int i, j, ns;for (mx = 0, i = n - 1; i >= 0; i--) {// vertex: 0 ~ n-1for (ns = 0, j = i + 1; j < n; j++)if (g[i][j]) stk[1][ ns++ ] = j;dfs(n, ns, 1); dp[i] = mx;}return mx;}/*==================================================*\| 欧拉路径O(E)| INIT: adj[][]置为图的邻接表; cnt[a]为a点的邻接点个数;| CALL: elpath(0); 注意:不要有自向边\*==================================================*/int adj[V][V], idx[V][V], cnt[V], stk[V], top;int path(int v){for (int w ; cnt[v] > 0; v = w) {stk[ top++ ] = v;w = adj[v][ --cnt[v] ];adj[w][ idx[w][v] ] = adj[w][ --cnt[w] ];// 处理的是无向图—-边是双向的，删除v->w后，还要处理删除w->v}return v;}void elpath (int b, int n){ // begin from b int i, j;for (i = 0; i < n; ++i) // vertex: 0 ~ n-1 for (j = 0; j < cnt[i]; ++j)idx[i][ adj[i][j] ] = j;printf("%d", b);for (top = 0; path(b) == b && top != 0; ) {b = stk[ --top ];printf("-%d", b);}printf("\n");}/*==================================================*\| Dijkstra数组实现O（N^2）| Dijkstra --- 数组实现(在此基础上可直接改为STL的Queue实现)| lowcost[] --- beg到其他点的最近距离| path[] -- beg为根展开的树，记录父亲结点\*==================================================*/#define INF 0x03F3F3F3Fconst int N;int path[N], vis[N];void Dijkstra(int cost[][N], int lowcost[N], int n, int beg){ int i, j, min;memset(vis, 0, sizeof(vis));vis[beg] = 1;for (i=0; i<n; i++){lowcost[i] = cost[beg][i]; path[i] = beg;}lowcost[beg] = 0;path[beg] = -1; // 树根的标记int pre = beg;for (i=1; i<n; i++){min = INF;dist[v] = dist[u] + c;for (j=0; j<n; j++)// 下面的加法可能导致溢出,INF 不能取太大if (vis[j]==0 &&lowcost[pre]+cost[pre][j]<lowcost[j]){lowcost[j] =lowcost[pre] + cost[pre][j]; path[j] = pre; } for (j=0; j<n; j++) if (vis[j] == 0 && lowcost[j] < min){ min = lowcost[j]; pre = j; } vis[pre] = 1; } } /*==================================================*\ | Dijkstra O(E * log E) | INIT: 调用init(nv, ne)读入边并初始化; | CALL: dijkstra(n, src); dist[i]为src 到i 的最短距离 \*==================================================*/ #define typec int // type of cost const typec inf = 0x3f3f3f3f; // max of cost typec cost[E], dist[V]; int e, pnt[E], nxt[E], head[V], prev[V], vis[V]; struct qnode { int v; typec c; qnode (int vv = 0, typec cc = 0) : v(vv), c(cc) {} bool operator < (const qnode& r) const { return c>r.c; } }; void dijkstra(int n, const int src){ qnode mv; int i, j, k, pre; priority_queue<qnode> que; vis[src] = 1; dist[src] = 0; que.push(qnode(src, 0)); for (pre = src, i=1; i<n; i++) { for (j = head[pre]; j != -1; j = nxt[j]) { k = pnt[j]; if (vis[k] == 0 && dist[pre] + cost[j] < dist[k]){ dist[k] =dist[pre] + cost[j]; que.push(qnode(pnt[j], dist[k])); prev[k] = pre; } } while (!que.empty() && vis[que.top().v] == 1) que.pop(); if (que.empty()) break ; mv = que.top(); que.pop(); vis[pre = mv.v] = 1; } } inline void addedge(int u, int v, typec c){ pnt[e] = v; cost[e] = c; nxt[e] = head[u]; head[u] = e++; } void init(int nv, int ne){ int i, u, v; typec c; e = 0;memset(head, -1, sizeof (head));memset(vis, 0, sizeof (vis));memset(prev, -1, sizeof (prev));for (i = 0; i < nv; i++) dist[i] = inf;for (i = 0; i < ne; ++i) {scanf("%d%d%d", &u, &v, &c);// %d: type of cost addedge(u, v, c); // vertex: 0 ~ n-1, 单向边 }}/*==================================================*\| BellmanFord 单源最短路O(VE)| 能在一般情况下，包括存在负权边的情况下，解决单源最短路径问题| INIT: edge[E][3]为边表| CALL: bellman(src);有负环返回0;dist[i]为src 到i 的最短距| 可以解决差分约束系统: 需要首先构造约束图，构造不等式时>=表示求最小值, 作为最长路，<=表示求最大值, 作为最短路 （v-u <= c:a[u][v] = c ）\*==================================================*/#define typec int // type of costconst typec inf=0x3f3f3f3f; // max of costint n, m, pre[V], edge[E][3];typec dist[V];int relax (int u, int v, typec c){if (dist[v] > dist[u] + c) {pre[v] = u; return 1; } return 0; } int bellman (int src){ int i, j;for (i=0; i<n; ++i) { dist[i] = inf; pre[i] = -1; } dist[src] = 0; bool flag; for (i=1; i<n; ++i){ flag = false; // 优化 for (j=0; j<m; ++j) { if( 1 == relax(edge[j][0], edge[j][1], edge[j][2]) ) flag = true; } if( !flag ) break; } for (j=0; j<m; ++j) { if (1 == relax(edge[j][0], edge[j][1], edge[j][2])) return 0; // 有负圈 } return 1; } /*==================================================*\ | SPFA(Shortest Path Faster Algorithm) Bellman-Ford 算法的一种队列实现，减少了不必要的冗余计算。

acm模板整理和使用方法[acm模板整理和使用方法]ACM模板指的是计算机科学中常用的算法模板，是计算机专业的学生在学习算法和数据结构时必需掌握的内容。

ACM模板整理和使用方法主要包括以下问题：一、为什么要使用ACM模板？ACM模板能使算法实现变得更简单、更方便、更快捷。

尤其在ACM竞赛中，使用优秀的模板可以节省编程时间，避免出现冗余代码，使得编程效率大幅提升。

二、哪些算法需要掌握？许多常见的算法，如快速排序、线段树、并查集、Kruskal算法、Dijkstra算法、最小生成树问题等，都需要掌握。

因此，算法学习和掌握是使用ACM模板的前提。

三、如何整理和使用ACM模板？1.整理ACM模板将常用的算法的代码整理，以函数或者类的形式存放在一个文件中。

注意代码要有良好的注释，易于阅读和理解。

2.旧的代码调试如果有其他ACM竞赛选手或者教练的旧代码，需要先将其调试通过。

因为在ACM比赛中，时间十分宝贵。

如果没有调试好的代码可以使用，建议可以使用OJ网站上的代码进行练习。

3.在比赛中使用和修改模板在ACM比赛中，选手需要快速编写正确的程序并提交到OJ网站。

使用模板可以节省时间和精力，但有时候需要针对具体的问题进行修改。

在修改时需要小心，一定要保证修改后的代码与原始模板的代码所实现的算法是等效的。

4.维护和更新模板ACM模板需要不断地维护和更新，特别是在涉及到新的算法或者数据结构时。

保证ACM模板的有效性和及时性非常重要，这需要持续的学习和探索。

四、如何学习和掌握ACM模板？1.选择学习和观察别人的代码一个好的方式是看国内和国际大佬们的代码，学习他们的代码风格和思考方式。

了解其他人的ACM模板如何实现，可以帮助你提高代码风格和技术水平。

2.探索自己不熟悉的算法和数据结构ACM竞赛中考察的算法不限于常见的算法，还包括各种数论、图论、动态规划等。

掌握这些算法和数据结构可以提高解题的速度和质量。

在掌握新算法之前，阅读相关论文或文章，掌握其基本原理和实现方法。

<数据结构>闭散列法整数hash#define max 4000037int hash[max],c[max];//hash存关键字，c存该位置关键字出现的次数bool use[max];int n,m,ans;int k[6],p[6];int locate(int k)//hash函数{int tmp;tmp = k;while(tmp<0)tmp+=max;while(tmp>=max)tmp-=max;while(use[tmp]&&hash[tmp]!=k){tmp++;if(tmp>=max)tmp-=max;}return tmp;}void insert(int k){int pos = locate(k);hash[pos] = k;use[pos] = 1;c[pos]++;}int onlyfind(int k){int pos = locate(k);if(hash[pos]==k)return c[pos];else return -1;}整数hash,开散列#include <stdio.h>#include <memory.h>#define MAX 3400000#define M 28999999int head[M],next[MAX];int lkey[MAX],up,ans;int n,m;int k[6],p[6];int hash(int key){int h;//h = ((key>>16)&&key)^(key>>8);h = ((~key)>>8)&&key ||( (key<<16) );h%=M;return h;}int find(int key){int h,p;h = hash(key);for(p=head[h];p>=0;p=next[p])if(lkey[p]==key)return 1;lkey[up] = key;next[up] = head[h];head[h] = up++;return -1;}int onlyfind(int key){int h,p;h = hash(key);for(p=head[h];p>=0;p=next[p])if(lkey[p]==key)return 1;return -1;}字符串hashint ELFhash(char *key) {unsigned h=0;while(*key) {h=(h<<4) + *key++;unsigned g=h & 0Xf0000000L;if(g) h^=g>>24;h &= ~g;}return h% M;}堆int heap[MAX+1],heapsize;void push(int key){int pos;pos = ++heapsize;while(pos>0&&heap[pos>>1]>key){heap[pos] = heap[pos>>1];pos>>=1;}heap[pos] = key;}void pop(){int key = heap[heapsize--];int pos,npos;pos = 1;npos = pos<<1;while(npos<=heapsize){if(npos+1<=heapsize&&heap[npos+1]<heap[npos])npos+=1;if(heap[npos]>=key)break;heap[pos] = heap[npos];pos = npos;npos = pos<<1;}heap[pos] = key;}二维树状数组int lowbit(int x){return x&(-x);}void updata(int x,int y,int w){int i,j;for(i=x;i<=n;i+=lowbit(i)){for(j=y;j<=n;j+=lowbit(j)){c[i][j]+=w;}}}int sum(int x,int y){int t=0,i,j;for(i=x;i>0;i-=lowbit(i)){for(j=y;j>0;j-=lowbit(j)){t+=c[i][j];}}return t;}Trie树#include<iostream>#define keyNum 26#define MaxN 50struct trie...{struct trieNode...{//trie结点的结构trieNode *link[keyNum];//下标为 'A' , 'B' , 'C' , , 'Z' 的指针数组 int num[keyNum];//插入key的次数trieNode()...{memset(num,0,sizeof(num));memset(link,NULL,sizeof(link));}void init()...{memset(link,NULL,sizeof(link));memset(num,0,sizeof(num));}};trieNode* root;trie()...{root=(trieNode*)malloc(sizeof(trieNode));//初始化时为root申请了空间 root->init();}bool Search(char *);void Insert(char []);void Delete(trieNode*);};bool trie::Search(char * x)...{if(*x==0)return false;trieNode* current=root;x++;while(*x)...{if(current->link[*(x-1)-'a'])current=current->link[*(x-1)-'a'];else break;x++;}if(*x==0&&current->num[*(x-1)-'a'])return true;else return false;}void trie::Delete(trieNode* t)...{int i;for(i=0;i<keyNum;i++)if(t->link[i])Delete(t->link[i]);memset(t->num,0,sizeof(t->num));delete(t);}void trie::Insert(char x[])...{trieNode *current=root;int i=1;while(x[i])...{if(current->link[x[i-1]-'a']==NULL)...{current->link[x[i-1]-'a']=(trieNode*)malloc(sizeof(trieNode)); (current->link[x[i-1]-'a'])->init();}current=current->link[x[i-1]-'a'];i++;}(current->num[x[i-1]-'a'])++;}char c[ 50000 ][MaxN],tmp;int main()...{trie a;int i=0,j,num;while(scanf("%s",c[i])!=EOF)a.Insert(c[i++]);num=i;for(i=0;i<num;i++)for(j=1;c[i][j];j++)...{tmp=c[i][j];c[i][j]=0;if(a.Search(c[i]))...{c[i][j]=tmp;if(a.Search(&c[i][j]))...{ printf("%s ",c[i]);break;}}else c[i][j]=tmp;}a.Delete(a.root);return 0;}二叉查找树//key是字符串#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct BiTNode{char data[31];struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;BiTree p=NULL;void InorderBST(BiTree T){if(T->lchild) InorderBST(T->lchild);printf("%s\n",T->data);if(T->rchild) InorderBST(T->rchild);}int SearchBST(BiTree T,char key[],BiTree f){int tmp1,tmp2;tmp1=tmp2=0;if(!T) {p=f;return 0;}\\找不到返回路径上最后一点else if(!strcmp(key,T->data)) {p=T;return 1;}else if(strcmp(key,T->data)<0) tmp1=SearchBST(T->lchild,key,T); else tmp2=SearchBST(T->rchild,key,T);if(tmp1||tmp2) return 1;else return 0;}BiTree InsertBST(BiTree T,char e[]){BiTree s;if(!SearchBST(T,e,NULL))//查找不到，（若已经存在则放弃）{s=(BiTree)malloc(sizeof(BiTNode));strcpy(s->data,e);s->lchild=s->rchild=NULL;if(!p) return s;else{if(strcmp(e,p->data)<0) p->lchild=s;else p->rchild=s;}}//else //若出现过做相应处理}/*int main(){BiTree T=NULL;char key[31];while(gets(key)!=NULL){if(T==NULL)T=InsertBST(T,key);//空树将返回指向根节点的指针else InsertBST(T,key);}InorderBST(T);return 0;}*/线段树#include<stdio.h>#include<memory.h>#define MAX 100001int up;int count[31];struct NODE{int l,r,flag;NODE *lcd,*rcd;void build(int i,int j);void insert(int i,int j,int k);void get(int i,int j);}node[MAX*4],*root=&node[0];void NODE::build(int i,int j){l=i;r=j;flag=1;if(l==r){lcd=rcd=NULL;}else{lcd=&node[up++];rcd=&node[up++];lcd->build(l,(l+r)/2);rcd->build((l+r)/2+1,r);}}void NODE::insert(int i,int j,int k) {if(i>r||j<l)return;if(i<=l&&j>=r){flag=k;return;}else{if(flag!=-1){lcd->insert(l,r,flag);rcd->insert(l,r,flag);}lcd->insert(i,j,k);rcd->insert(i,j,k);flag=-1;}}void NODE::get(int i,int j){if(i>r||j<l)return;if(flag!=-1){count[flag]=1;}else{lcd->get(i,j);rcd->get(i,j);}}int main(){int l,t,o,i,j,k,ans;char s[5];// freopen("in.txt","r",stdin);scanf("%d%d%d",&l,&t,&o);up=1;root->build(1,l);while(o--){scanf("%s",s);if(s[0]=='C'){scanf("%d%d%d",&i,&j,&k);root->insert(i,j,k);}else{scanf("%d%d",&i,&j);memset(count,0,sizeof(count));root->get(i,j);ans=0;for(i=1;i<=t;i++){if(count[i]){ans++;}}printf("%d\n",ans);}}return 0;}线段树动态运用#include<stdio.h>#include<memory.h>#include<algorithm>using namespace std;#define MAXN 1000001#define MAXM 50001int value[MAXN],dog[MAXN],b[MAXM],e[MAXM],rank[MAXM],ans[MAXM],ind[MAXM]; int up=1;struct NODE{int now,count;NODE *rcd,*lcd;void build(int i,int j);void insert(int key);void dele(int key);int get(int k);}node[MAXN*4],*root=&node[0];bool cmp(int p,int q){return b[p]<b[q]||b[p]==b[q]&&e[p]<e[q];}void NODE::build(int i,int j){now=(i+j)/2;if(i==j){lcd=rcd=NULL;}else{lcd=&node[up++];rcd=&node[up++];lcd->build(i,(i+j)/2);rcd->build((i+j)/2+1,j);}}void NODE::insert(int key){count++;if(lcd==NULL)return;if(key<=value[now]){lcd->insert(key);}else{rcd->insert(key);}}void NODE::dele(int key){count--;if(lcd==NULL)return;if(key<=value[now]){lcd->dele(key);}else{rcd->dele(key);}}int NODE::get(int k){if(lcd==NULL)return value[now];if(lcd->count>=k){return lcd->get(k);}else{return rcd->get(k-lcd->count);}}int main(){int n,m,i,j;// freopen("d:/in.txt","r",stdin);scanf("%d%d",&n,&m);for(i=0;i<n;i++){scanf("%d",&dog[i]);value[i]=dog[i];}sort(value,value+n);n=unique(value,value+n)-value;root->build(0,n-1);for(i=0;i<m;i++){scanf("%d%d%d",&b[i],&e[i],&rank[i]);b[i]--;e[i]--;ind[i]=i;}sort(ind,ind+m,cmp);for(i=b[ind[0]];i<=e[ind[0]];i++){root->insert(dog[i]);}ans[ind[0]]=root->get(rank[ind[0]]);for(i=1;i<m;i++){for(j=b[ind[i-1]];j<b[ind[i]];j++){root->dele(dog[j]);}for(j=e[ind[i-1]]+1;j<=e[ind[i]];j++){root->insert(dog[j]);}ans[ind[i]]=root->get(rank[ind[i]]);}for(i=0;i<m;i++){printf("%d\n",ans[i]);}return 0;}RMQvoid RMQ(int M[MAXN][LOGMAXN], int A[MAXN], int N){int i, j;//initialize M for the intervals with length 1for (i = 0; i < N; i++)M[i][0] = i;//compute values from smaller to bigger intervalsfor (j = 1; 1 << j <= N; j++)for (i = 0; i + (1 << j) - 1 < N; i++)if (A[M[i][j - 1]] < A[M[i + (1 << (j - 1))][j - 1]]) M[i][j] = M[i][j - 1];elseM[i][j] = M[i + (1 << (j - 1))][j - 1];}//产生的M[i][j]为[ i , j ]中最小的数//查询：[ l , r ]//k:=ln((r-l+1)/ln(2)); ans:=min(M[l，k],M[r-2^k+1,k]);LCA+RMQ#include <stdio.h>#include <math.h>#include <memory.h>#define MAX 1000int tree[MAX][MAX],first[MAX];int len[MAX],count[MAX];int node[2*MAX],deep[2*MAX],top;int M[MAX][32],in[MAX];int N;void dfs(int u,int pre,int d){int i,t;node[top] = u;deep[top] = d;if(first[u]==-1)first[u] = top;top++;for(i=0;i<len[u];i++){t = tree[u][i];if(pre==t)continue;dfs(t,u,d+1);node[top] = u;deep[top] = d;top++;}}void RMQ_init(){int i,j;for(i=0;i<top;i++)M[i][0] = i;for(j=1;(1<<j)<=top;j++)for(i=0;i+(1<<j)-1<top;i++)if(deep[M[i][j-1]]<deep[M[i+(1<<(j-1))][j-1]]) M[i][j] = M[i][j-1];elseM[i][j] = M[i+(1<<(j-1))][j-1];}int RMQ_query(int u,int v){int l,r,t;l = first[u];r = first[v];if(l>r){t = l;l = r;r = t;}t = log((double)(r-l+1))/log(2.0);if(deep[M[l][t]]<=deep[M[r-(1<<t)+1][t]]) return node[M[l][t]];elsereturn node[M[r-(1<<t)+1][t]];}int main(){//freopen("in.txt","r",stdin);int i,u,v,k,j,T,s;char ch;while(scanf("%d",&N)!=EOF){memset(len,0,sizeof(len));memset(in,0,sizeof(in));for(i=1;i<=N;i++){scanf("%d",&u);while((ch=getchar())!=':');while((ch=getchar())!='(');scanf("%d",&k);while((ch=getchar())!=')');for(j=1;j<=k;j++){scanf("%d",&v);in[v]++;tree[u][len[u]++] = v;//tree[v][len[v]++] = u;}}top = 0;memset(first,-1,sizeof(first));for(i=1;i<=N;i++)if(in[i]==0){s = i;break;}dfs(s,-1,0);RMQ_init();scanf("%d",&T);memset(count,0,sizeof(count));for(i=1;i<=T;i++){while((ch=getchar())!='(');scanf("%d%d",&u,&v);while((ch=getchar())!=')');s = RMQ_query(u,v);count[s]++;}for(i=1;i<=N;i++)if(count[i]>0)printf("%d:%d\n",i,count[i]);}return 0;}SB-Tree#include <stdio.h>int n,f;void solve(int a,int b,int c,int d){ //0,1,1,1if (b+d>n) return;solve(a,b,a+c,b+d);if(f){printf("%d/%d",a+c,b+d);f=0;}elseprintf(",%d/%d",a+c,b+d);solve(a+c,b+d,c,d);};int main(){int T;scanf("%d",&T);while(T--){scanf("%d",&n);f=1;solve(0,1,1,1);printf("\n");}return 0;}。

0.头文件#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>using namespace std;const int maxn = 110;1.const int INF = 0x3f3f3f3f;经典1.埃拉托斯特尼筛法/*|埃式筛法||快速筛选素数||16/11/05ztx|*/int prime[maxn];bool is_prime[maxn];int sieve(int n){int p = 0;for(int i = 0; i <= n; ++i)is_prime[i] = true;is_prime[0] = is_prime[1] = false;for (int i = 2; i <= n; ++i){ // 注意数组大小是nif(is_prime[i]){prime[p++] = i;for(int j = i + i; j <= n; j += i) // 轻剪枝，j必定是i的倍数is_prime[j] = false;}}return p; // 返回素数个数}2.快速幂/*|快速幂||16/11/05ztx|*/typedef long long LL; // 视数据大小的情况而定LL powerMod(LL x, LL n, LL m){LL res = 1;while (n > 0){if (n & 1) // 判断是否为奇数，若是则true res = (res * x) % m;x = (x * x) % m;n >>= 1; // 相当于n /= 2;}return res;}3.大数模拟大数加法/*|大数模拟加法||用string模拟||16/11/05ztx, thanks to caojiji|*/string add1(string s1, string s2){if (s1 == "" && s2 == "") return"0";if (s1 == "") return s2;if (s2 == "") return s1;string maxx = s1, minn = s2;if (s1.length() < s2.length()){maxx = s2;minn = s1;}int a = maxx.length() - 1, b = minn.length() - 1;for (int i = b; i >= 0; --i){maxx[a--] += minn[i] - '0'; // a一直在减，额外还要减个'0'}for (int i = 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;}return maxx;}大数阶乘/*|大数模拟阶乘||用数组模拟||16/12/02ztx|*/#include <iostream>#include <cstdio>using namespace std;typedef long long LL;const int maxn = 100010;int num[maxn], len;/*在mult函数中，形参部分：len每次调用函数都会发生改变，n 表示每次要乘以的数，最终返回的是结果的长度tip: 阶乘都是先求之前的(n-1)!来求n!初始化Init函数很重要，不要落下*/void Init() {len = 1;num[0] = 1;}int mult(int num[], int len, int n) {LL tmp = 0;for(LL i = 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;}return len;}int main() {Init();int n;n = 1977; // 求的阶乘数for(int i = 2; i <= n; ++i) {len = mult(num, len, i);}for(int i = len - 1; i >= 0; --i)printf("%d",num[i]); // 从最高位依次输出,数据比较多采用printf输出printf("\n");return0;}4.GCD/*|辗转相除法||欧几里得算法||求最大公约数||16/11/05ztx|*/int gcd(int big, int small){if (small > big) s, small);int temp;while (small != 0){ // 辗转相除法if (small > big) s, small); temp = big % small;big = small;small = temp;}return(big);}5.LCM/*|辗转相除法||欧几里得算法||求最小公倍数||16/11/05ztx|*/int gcd(int big, int small){if (small > big) s, small);int temp;while (small != 0){ // 辗转相除法if (small > big) s, small);temp = big % small;big = small;small = temp;}return(big);}6.全排列/*|求1到n的全排列, 有条件||16/11/05ztx, thanks to wangqiqi|*/void Pern(int list[], int k, int n) { // k表示前k 个数不动仅移动后面n-k位数if (k == n - 1) {for (int i = 0; i < n; i++) {printf("%d", list[i]);}printf("\n");}else {for (int i = k; i < n; i++) { // 输出的是满足移动条件所有全排列s[k], list[i]);Pern(list, k + 1, n);s[k], list[i]);}}}7.二分搜索/*|二分搜索||要求：先排序||16/11/05ztx, thanks to wangxiaocai|*/// left为最开始元素, right是末尾元素的下一个数，x是要找的数int bsearch(int *A, int left, int right, int x){int m;while (left < right){m = left + (right - left) / 2;if (A[m] >= x) right = m; else left = m + 1;// 如果要替换为 upper_bound, 改为:if(A[m] <= v) x = m+1; else y = m;}return left;}/*最后left == right如果没有找到135577找6，返回7如果找有多少的x，可以用lower_bound查找一遍，upper_bound查找一遍，下标相减C++自带的lower_bound(a,a+n,x)返回数组中最后一个x的下一个数的地址upper_bound(a,a+n,x)返回数组中第一个x的地址如果a+n内没有找到x或x的下一个地址，返回a+n的地址lower_bound(a,a+n,x）-upper_bound(a,a+n,x)返回数组中x的个数*/数据结构并查集8.并查集/*|合并节点操作||16/11/05ztx, thanks to chaixiaojun|*/int father[maxn]; // 储存i的father父节点void makeSet() {for (int i = 0; i < maxn; i++)father[i] = i;}int findRoot(int x) { // 迭代找根节点int root = x; // 根节点while (root != father[root]) { // 寻找根节点root = father[root];}while (x != root) {int tmp = father[x];father[x] = root; // 根节点赋值x = tmp;}return root;}void Union(int x, int y) { // 将x所在的集合和y所在的集合整合起来形成一个集合。

目录目录 (1)一．扩展的欧几里德和不定方程的解 (2)二．中国同余定理 (3)三．原根 (5)四．积性函数 (6)五．欧拉函数性质 (7)六．线性求1-max的欧拉函数值 (9)七．求单个欧拉函数，求最小的x(phi（n）%x==0),使得2^x =1(mod n) (10)一．扩展的欧几里德和不定方程的解解不定方程ax + by = n的步骤如下:(1)计算gcd(a, b). 若gcd(a, b)不能整除n，则方程无整数解；否则，在方程的两边同除以gcd(a, b)，得到新的不定方程a'x + b'y = n'，此时gcd(a', b') = 1(2)求出不定方程a'x + b'y = 1的一组整数解x0, y0，则n'x0，n'y0是方程a'x + b'y = n'的一组整数解。

(3)根据扩展欧几里德定理，可得方程a'x + b'y = n'的所有整数解为：x = n'x0 + b'ty = n'y0 - a't(t为整数)这也就是方程ax + by = n的所有整数解利用扩展的欧几里德算法，计算(a, b)和满足gcd = (a, b) = ax0 + by0的x0和y0，也就是求出了满足a'x0 + b'y0 = 1的一组整数解。

因此可得：x = n/gcd * x0 + b/gcd * ty = n/gcd * y0 - a/gcd * t(t是整数)int extend_Euclid(int a, int b, int &x, int &y){if (b == 0){x = 1;y = 0;return a;}int gcd= extend_Euclid ( b, a % b, x, y );int temp = x;x = y;y = temp - (a / b) * y;return gcd;}二．中国同余定理Poj 2891#include<stdio.h>#include<iostream>using namespace std;__int64 GCD(__int64 i,__int64 j){if(j==0)return i;elsereturn GCD(j,i%j);}__int64 extend_Euclid(__int64 a, __int64 b, __int64 &x, __int64 &y) {if (b == 0){x = 1;y = 0;return a;}__int64 gcd= extend_Euclid ( b, a % b, x, y );__int64 temp = x;x = y;y = temp - (a / b) * y;return gcd;}//只有两个式子的中国同余定理，return z=a*xx+x=b*yy+y;__int64 CRT_2(__int64 a,__int64 x,__int64 b,__int64 y){__int64 xx,yy,gcd;gcd=extend_Euclid(a,b,xx,yy);__int64 c=y-x;while(c<0)c+=a;if(c%gcd!=0)return -1;xx*=c/gcd;yy*=c/gcd;__int64 t=yy/(a/gcd);while(yy-t*(a/gcd)>0)t++;while(yy-(t-1)*(a/gcd)<=0)t--;return (t*(a/gcd)-yy)*b+y;}//chinese remainder theorem//crt[i][0]存的是除数，crt[i][1]存的是余数,0<=i<n,n>1,返回结果,-1表示无解__int64 CRT(__int64 crt[][2],int n){__int64 m=crt[0][0]/GCD(crt[0][0],crt[1][0])*crt[1][0]; //最大公约数__int64 ans=CRT_2(crt[0][0],crt[0][1],crt[1][0],crt[1][1])%m;for(int i=2;i<n&&ans!=-1;i++){ans=CRT_2(m,ans,crt[i][0],crt[i][1]);m*=crt[i][0]/GCD(m,crt[i][0]);ans%=m;}return ans;}int main(void){int n;__int64 a[10000][2];while(scanf("%d",&n)==1){for(int i=0;i<n;i++)scanf("%I64d%I64d",&a[i][0],&a[i][1]);if(n==1)printf("%I64d\n",a[0][1]);elseprintf("%I64d\n",CRT(a,n));}return 0;}三．原根Poj 1284 ans=φ（p-1）;//p是素数设h为一整数，n为一正整数，（h，n）=k，适合h^k=1（mod n）的最小正整数k叫做h对n的次数。