上海交通大学ACM算法模板

ACM算法模板集Contents.常用函数与STL.重要公式与定理FibonacciNumberLucasNumberCatalanNumberStirlingNumber（SecondKind）BellNumberStirling'sApproximationSumofReciprocalApproximationYoungTableau整数划分错排公式三角形内切圆半径公式三角形外接圆半径公式圆内接四边形面积公式基础数论公式.大数模板，字符读入.数论算法GreatestCommonDivisor最大公约数Prime素数判断SievePrime素数筛法ModuleInverse模逆元ExtendedEuclid扩展欧几里德算法ModularLinearEquation模线性方程（同余方程）ChineseRemainderTheorem中国余数定理（互素于非互素）EulerFunction欧拉函数Farey总数Farey序列构造Miller_Rabbin素数测试，Pollard_rho因式分解五.图论算法.最小生成树（Kruscal算法）.最小生成树（Prim算法）.单源最短路径（Bellman-ford算法）.单源最短路径（Dijkstra算法）.全源最短路径（Folyd算法）.拓扑排序.网络预流和最大流.网络最小费用最大流.网络最大流（高度标号预流推进）.最大团.二分图最大匹配（匈牙利算法）.带权二分图最优匹配（KM算法）.强连通分量（Kosaraju算法）.强连通分量（Gabow算法）.无向图割边割点和双连通分量.最小树形图0（N人3）.最小树形图O（VE）六.几何算法.几何模板.球面上两点最短距离.三点求圆心坐标.三角形几个重要的点七.专题讨论.树状数组.字典树.后缀树.线段树.并查集.二叉堆.逆序数（归并排序）.树状DP.欧拉路.八数码.高斯消元法.字符串匹配（KMP算法）.全排列，全组合.二维线段树.稳定婚姻匹配.后缀数组.左偏树.标准RMQ-ST.度限制最小生成树.最优比率生成树（0/1分数规戈I）.最小花费置换.区间K大数.LCA-RMQ-ST.LCA-larjan.指数型母函数.指数型母函数(大数据).单词前缀树(字典树+KMP).FFT(大数乘法).二分图网络最大流最小割.混合图欧拉回路.无源汇上下界网络流.二分图最小点权覆盖.带约束的轨道计数(Burnside引理).三分法求函数波峰.单词计数，矩阵乘法.字符串和数值hash.滚动队列，前向星表示法.最小点基，最小权点基第一章常用函数和STL一.常用函数#include<stdio.h>intgetchar(void); 〃读取一个字符/一般用来去押无用字箱char*gets(char*str); 〃读取一行字符串#include<stdlib.h>void*malloc(size_tsize); 〃动态内存分配，开辟大小为size的空间voidqsort(void*bufzsize_tnum,size_tsize,int(*compare)(constvoid*,constvoid*)); 〃快速排序Sample:intcompare_ints(constvoid*a,constvoid*b){int*argl=(int*)a;int*arg2=(int*)b;if(*argl<*arg2)return-1;elseif(*argl==*arg2)return0;elsereturn1;}intarray[]={-2,99z0,-743,2,3,4};intarray_size=7;qsort(array,array_size,sizeof(int)zcomparejnts);#include<math.h>〃求反正弦，argeH,l]z返回值w[-pi/2,+pi/2]doubleasin(doublearg);〃求正弦，arg为弧度,弧度=角度*Pi/180.0,返回值1]doublesin(doublearg);〃求e的arg次方doubleexp(doublearg);〃求num的对数，基数为edoublelog(doublenum);〃求num的根

doublesqrt(doublenum);〃求base的exp次方doublepow(doublebase,doubleexp);#include<string.h>〃初始化内存，常用来初始化数组void*memset(void*buffer;intchzsize_tcount);memset(the_arrayz0,sizeof(the_array));〃printf是它的变形，常用来将数据格式化为字符串intsprintf(char*buffer;constchar"format,...);sprintf(s,"%d%d"/123z4567);//s=n1234567n〃scanf是它的变形，常用来从字符串中提取数据intsscanf(constchar*buffer;constchar"format,...);Sample:charresult[100]="24hello",str[100];intnum;sprintf(result,"%d%s'\numzstr);//num=24;str=,'hellon;〃字符串比较，返回值vO代表strlvstr2,=0代表strl=str2,>0代表st「l>str2intstrcmp(constchar*strlzconstchar*str2);常用STL[标准container概要]vector<T>list<T>vector<T>list<T>queue<T>stack<T>priority_queue<T>set<T>map<key,val>队列，empty()zfront()zpop()zpush()栈,empty(),top(),pop(),push()优先队列，empty(),top(),pop(),push()集合关联数组，常用来作hash映射[标准algorithm摘录]for_each()find()replace()copy()remove()reverse()sort()partial_sort()binary_search()merge()对每一个元素都唤起(调用)一个函数查找第一个能与引数匹配的元素用新的值替换元素，O(N)复制(拷贝)元素，O(N)移除元素倒置元素for_each()find()replace()copy()remove()reverse()sort()partial_sort()binary_search()merge()排序，O(Nlog(N))部分排序二分查找合并有序的序列，0(N)[C++String摘录]copy()empty()从别的字符串拷贝判断字符串是否为空

copy()empty()从别的字符串拷贝判断字符串是否为空erase() 从字符串移除元素find() 查找元素insert() 插入元素length() 字符串长度replace。 替换元素substr() 取子字符串swap() 交换字符串第二章重要公式与定理FibonacciNumber0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610...Formula:F[0]=0;F[l]=1；F[i]=F[i-l]+F[i-2],^(i+1 1+75p.F[n]= = -=l~^——12血V5 V5| 2jILucasNumber1,3,4,7,11,18,29,47,76,123...Formula:L[n]=nL[n]=nCatalanNumber1,2,5,14,42,132,429,1430,4862,16796,58786,208012...Formula:C(2n,n)Cln]=—~—(n+1)n=3;Application:1)将n=3;Application:1)将n+2边形沿弦切割成n个三角形的不同切割数n+1个数相乘，给每两个元素加上括号的不同方法数Sample:n=2;(1(23)),((12)3)n=3；(1(2(34))),(1((23)4)),((12)(34)),((1(23))4),(((12)3)4)n个节点的不同形状的二叉树数(严《数据结构》P.155)4)从n*n方格的左上角移动到右下角不升路径数Sample:StirlingNumber(SecondKind)S(n,m)表示含n个元素的集合划分为m个集合的情况数或者是n个有标号的球放到m个无标号的盒子中，要求无一为空，其不同的方案数Formula:r0(m=0arn<m)S(n,m)=<S(n-1,m-1)+m*S(n-1,m)(n>m't1)S(n,m)=—》(-1/*C(m,i)*(m-i)nm!i=oSpecialCases:s(n,o)=oS(n,1)=1S(n,2)=2nl-lS(n,3)=—(3n-3w2n+3)6S(n,n-1)=C(nz2)S(n,n)=1BellNumbern个元素集合所有的划分数Formula:nB[nl=2S(n,i)

£=0Stirling'sApproximationSumofReciprocalApproximationEulerGamma=0.57721566490153286060651209;(11>一=lii(n)+EikLexGanvna:(n-»co).YoungTableauYoungTableau(杨式图表)是一个矩阵，它满足条件：如果格子[i,j]没有元素，贝旺i+1,"也一定没有元素如果格子[i,j]有元素a[i,j],则[i+1,j]要么没有元素，要么a[i+l,j]>a[i,j]Y[n]代表n个数所组成的杨式图表的个数Formula:Y[l]=1;Y[2]=2;Y(n]=Y[n-1]+(n-1)*Y[n-2];(n>2).整数划分将整数n分成k份，且每份不能为空，任意两种分法不能相同1)不考虑顺序for(intp=l;p<=n;p++)for(inti=p;i<=n;i++)for(intj=k;j>=l;j-)dp[i][j]+=dp[i-p][j-l];cout<<dp[n][k]<<endl;2)考虑顺序dp[i][j]=dp[i-k]U-l]；(k=l..i)3)若分解出来的每个数均有一个上限mdp[i][j]=dp[i-k][j-1];(k=l..m).错排公式d[l]=0, d[2]=1,d[n]=(n-1)*(d[n-1]+d[n-2]);.三角形内切圆半径公式2Sr= ；a+b+cp=(a+b+c)/2;S=Vp(p-a)(p-b)(p-c);.三角形外接圆半径公式abcR=k.圆内接四边形面积公式a+b*c+dP=——2 ；S=V(p-a)(p-b)(p-c)(p-d);.基础数论公式1)模取募an%b=((((a*b)*a)%b)...)%b;n的约数的个数n= *32^*33^*.・.*31nll若n满足 ,则n的约数的个数为(ill+1)(112+1)(113+1)...(inn+1);第三章大数模板typedefinthugeint;〃应不大于，以防乘法时溢出constintBase=1000;constintCapacity=1000;structxnum{intLen;intData[Capacity];xnum():Len(0){}xnum(constxnum&V):Len(V.Len){memcpy(Dataz\/.DatazLen*sizeof*Data);}xnum(intV):Len(O){for(；V>0;V/=Base)Data[Len++]=V%Base;}xnum(charS[]);xnum&operator=(constxnum&V){Len=V.Len;memcpy(DatazV.Data,Len*sizeof*Data);return*this;}int&operator[](intIndex){returnData[Index];}intoperator[](intIndex)const{returnData[Index];}voidprint(){printf("%d"zLen==O?O:Data[Len-l]);for(inti=Len-2;i>=0;i)for(intj=Base/10;j>0;j/=10)printf("%d"zData[i]/j%10);}};xnum::xnum(charS[]){intI,J;Data[Len=0]=0;J=1;for(I=strlen(S)-l;I>=0;I-){Data[Len]+=(S[I]-'0')*J;J*=10;if(J>=Base)J=1,Data[++Len]=0;}if(Data[Len]>0)Len++;}intcompare(constxnum&Azconstxnum&B){inti;if(A.Len!=B.Len)returnA.Len>B.Len?1:-1;for(I=A.Len-1;I>=0&&A[I]==B[I];I-);if(I<0)return0;returnA[I]>B[I]?1:-1;}xnumoperator+(constxnum&Azconstxnum&B){xnumR;intI;intCarry=0;for(I=0;I<A.Len11I<B.Len11Carry>0;I++){if(I<A.Len)Carry+=A[I];if(I<B.Len)Carry+=B[I];R[I]=Carry%Base;Carry/=Base;}R.Len=I;returnR;}xnumoperator-(constxnum&Azconstxnum&B){xnumR;intCarry=0;R.Len=A.Len;intI;for(I=0;I<R.Len;I++){R[I]=A[I]-Carry;if(I<B.Len)R[I]-=B[I];if(R[I]<0)Carry=1,R[I]+=Base;elseCarry=0;}while(R.Len>0&&R[R.Len-1]==0)R.Len-;returnR;}xnumoperator*(constxnum&A,constintB){intI;if(B==0)return0;xnumRjhugeintCarry=0;for(I=0;I<A.Len11Carry>0;I++){if(I<A.Len)Carry+=hugeint(A[I])*B;R[I]=Carry%Base;Carry/=Base;}R.Len=I;returnR;}xnumoperator*(constxnum&A,constxnum&B){inti;if(B.Len==0)return0;xnumR;for(I=0;I<A.Len;I++){hugeintCarry=0;for(intJ=0;J<B.Len11Carry>0;J++){if(J<B.Len)Carry+=hugeint(A[I])*B[J];if(I+J<R.Len)Carry+=R[I+J];if(I+J>=R.Len)R[R.Len++]=Carry%Base;elseR[I+J]=Carry%Base;Carry/=Base;}}returnR;}xnumoperator/(constxnum&A,constintB){xnumR;intI;hugeintC=0;for(I=A.Len-1;I>=0;I-){C=C*Base+A[I];R[I]=C/B;C%=B;}R.Len=A.Len;while(R.Len>0&&R[R.Len-1]==0)R.Len—;returnR;}//divxnumoperator/(constxnum&A,constxnum&B){intI;xnumRzCarry=0;intLeft,Right,Mid;for(I=A.Len-1;I>=0;I-){Carry=Carry*Base+A[I];Left=0;Right=Base-1;while(Left<Right){Mid=(Left+Right+1)/2;if(compare(B*Mid,Carry)<=0)Left=Mid;elseRight=Mid-1;}R[I]=Left;Carry=Carry-B*Left;}R.Len=A.Len;while(R.Len>0&&R[R.Len-1]==0)R.Len—;returnR;}//modxnumoperator%(constxnum&A,constxnum&B){intI;xnumRzCarry=0;intLeft,Right,Mid;for(I=A.Len-1;I>=0;I-){Carry=Carry*Base+A[I];Left=OjRight=Base-1;while(Left<Right){Mid=(Left+Right+1)/2;if(compare(B*Mid,Carry)<=0)Left=Mid;elseRight=Mid-1;}R[I]=Left;Carry=Carry-B*Left;}R.Len=A.Len;while(R.Len>0&&R[R.Len-1]==0)R.Len-;returnCarry;}istream&operator>>(istream&In,xnum&V){charCh;for(V=0;In>>Ch;){V=V*10+(Ch-'0');if(cin.peek()<=',)break;}returnIn;}ostream&operator<<(ostream&Out,constxnum&V){intI;Out<<(V.Len==0?0:V[V.Len-1]);for(I=V.Len-2;I>=0;I-)for(intJ=Base/10;J>0;J/=10)Out<<V[I]/J%10;returnOut;}xnumgcd(xnumazxnumb){if(compare(b,0)==0)returna;elsereturngcd(b,a%b);}intdiv(char*A,intB){intI;intC=0;intAlen=strlen(A);for(I=0;I<Alen;1++){C=C*Base+ %=B;}returnC;}xnumC(intnjntm){inti;xnumsum=1;for(i=n;i>=n-m+l;i--)sum=sum*i;for(i=1;i<=m;i++)sum=sum/i;returnsum;}#defineMAXN9999#defineDLEN4classBigNum{private:inta[1000];〃可以控制人数的位数intlen;〃大数长度public:BigNum(){len=1;memset(az0zsizeof(a));}BigNum(constint);BigNum(constchar*);BigNum(constBigNum&);BigNum&operator=(constBigNum&);BigNumoperator+(constBigNum&)const;BigNumoperator-(constBigNum&)const;BigNumoperator*(constBigNum&)const;BigNumoperator/(constint&)const;BigNumoperator人(constint&)const;intoperator%(constint&)const;booloperator>(constBigNum&T)const;voidprint();};BigNum::BigNum(constintb){intc,d=b;len=0;memset(a,0,sizeof(a));while(d>MAXN){c=d-(d/(MAXN+1))*(MAXN+l);d=d/(MAXN+1);a[len++]=c;}a[len++]=d;}BigNum::BigNum(constchar*s){intt,k,index/,i;memset(azOzsizeof(a));l=strlen(s);len=l/DLEN;if(l%DLEN)len++;index=0;for(i=l-l;i>=0;i-=DLEN){t=O;k=i-DLEN+l;if(k<O)k=O;for(intj=k;j<=i;j++)t=t*10+s[j]-'0';a[index4-4-]=t;}}BigNum::BigNum(constBigNum&T):len(T.len){inti;memset(a,0zsizeof(a));for(i=0;i<len;i++)a[i]=T.a[i];}BigNum&BigNum::operator=(constBigNum&n){len=n.len;memset(a,Ozsizeof(a));inti;for(i=0;i<len;i++)a[i]=n.a[i];return*this;}BigNumBigNum::operator+(constBigNum&T)const{BigNumt(*this);inti,big;〃位数big=T.len>len?T.len:len;for(i=0;i<big;i++){t.a[i]+=T.a[i];if(t.a[i]>MAXN){t.a[i+1]++;t.a[i]-=MAXN+1;}>if(t.a[big]!=0)t.len=big+l;elset.len=big;returnt;}BigNumBigNum::operator-(constBigNum&T)const{intiJ,big;boolflag;BigNumtl,t2;if(*this>T){tl=*this;t2=T;flag=0;}else{tl=T;t2=*this;flag=l;}big=tl.len;for(i=0;i<big;i++){if(tl.a[i]<t2.a[i]){j=i+1;while(tl.a[j]==0)j++；tl.a[j-]—;while(j>i)tl.a[j-]+=MAXN;tl.a[i]+=MAXN+1-t2.a[i];}elsetl.a[i]-=t2.a[i];}tl.len=big;while(tl.a[len-1]==0&&tl.len>1){tl.len—;big—;}if(flag)tl.a[big-l]=O-tl.a[big-l];returntl;}BigNumBigNum::operator*(constBigNum&T)const{BigNumret;inti,j,up;inttemp,templ;for(i=0;i<len;i++){up=0;for(j=0;j<T.len;j++){temp=a[i]*T.a[j]+ret.a[i+j]+up;if(temp>MAXN){tempi=temp-temp/(MAXN+1)*(MAXN+1);up=temp/(MAXN+l);ret.a[i+j]=tempi;}else{up=0;ret.a[i+j]=temp;}}if(up!=0)ret.a[i+j]=up;}ret.len=i+j；while(ret.a[ret.len-1]==0&&ret.len>1)ret.len--;returnret;}BigNumBigNum::operator/(constint&b)const(BigNumret;intizdown=0;for(i=len-1;i>=0;i-){ret.a[i]=(a[i]+down*(MAXN+1))/b;down=a[i]+down*(MAXN+1)-ret.a[i]*b;}ret.len=len;while(ret.a[ret.len-1]==0&&ret.len>1)ret.len—;returnret;}intBigNum::operator%(constint&b)const{inti,d=O;for(i=len-1;i>=0;i-){d=((d*(MAXN+l))%b+a[i])%b;}returnd;}BigNumBigNum::operatorA(constint&n)const{BigNumtzret(l);if(n<O)exit(-l);if(n==O)return1;if(n==l)return*this;intm=n;while(m>l){t=*this;inti;for(i=l;i<<l<=m;i<<=l){t=t*t;}m-=i;ret=ret*t;if(m==l)ret=ret*(*this);}returnret;}boolBigNum::operator>(constBigNum&T)const{intIn;if(len>T.len)returntrue;elseif(len==T.len){In=len-1;while(a[ln]==T.a[ln]&&In>=0)In--;if(ln>=0&&a[ln]>T.a[ln])returntrue;elsereturnfalse;}elsereturnfalse;}voidBigNum::print(){inti;cout<<a[len-1];for(i=len-2;i>=0;i—){cout.widthCDLENJjcout.fillCO^jcout<<a[i];}}〃读取整数constintok=1;intget_val(int&ret){ret=0;charch;while((ch=getchar())>'9'11ch<,0');do{ret=ret*10+ch-'O';}while((ch=getchar())<='9'&&ch>=*0');returnok;}〃带负数intget_val(int&ret){ret=0;charch;boolneg=false;while(((ch=getchar())>'9'11ch<,0')&&ch!='-');if(ch==*-*){neg=true;while((ch=getchar())>'9'11ch<'0');}do{ret=ret*10+ch-10';}while((ch=getchar())<='9*&&ch>=*0');ret=(neg?-ret:ret);returnok;}〃读取整数，可判EOF和EOLconstinteof=-l;constinteol=-2;intget_val(int&ret){ret=Ojcharch;while(((ch=getchar())>'9'||ch<*0,)&&ch!=EOF);if(ch==EOF)returneof;do{ret=ret*10+ch-'0,;}while((ch=getchar())<='9,&&ch>=*0,);if(ch==*\n')returneol;returnok;}〃读取浮点数intget_val(double&ret){ret=Ojdoublebase=O.ljcharch;booldot=false,neg=false;while(((ch=getchar())>'9'11ch<,0')&&ch!= &&ch!=;if(ch=={neg=true;while(((ch=getchar())>*9'11ch<,0')&&ch!=&&ch!=*-');}do{if(ch=={dot=true;continue;}if(dot){ret+=(ch-'O')*base;base*=0.1;}elseret=ret*10+(ch-'O1);}while(((ch=getchar())<=,9'&&ch>=*0')11ch==''');ret=(neg?-ret:ret);returnok;}第四章数论算法GreatestCommonDiviso「最大公约数intGCD(intx,inty){intt;while(y>0){t=x%y;x=y;y=t;}returnx;}Prime素数判断boolis_prime(intu){if(u==011u==1)returnfalse;if(u==2) returntrue;if(u%2==0) returnfalse;for(inti=3;i<=sqrt(u)；i+=2)if(u%i==O)returnfalse;returntrue;}SievePrime素数筛法constintM=1000;//M:sizeboolmark[M];//true:primenumbervoidsieve_prime(){memset(mark,true,sizeof(mark));mark[0]=mark[l]=false;for(inti=2;i<=sqrt(M);i++){if(mark[i]){for(intj<M;j+=i)mark[j]=false;}}}ModuleInverse模逆元//ax=1(modn)intInv(inta,intn){intd,x,y;d=extended_euclid(aznzx,y);if(d==1)return(x%n+n)%n;elsereturn-1;//nosolution}ExtendedEuclid扩展欧几里德算法〃如果GCD(azb)=d,则存在x,y,使d=ax+by//extended_euclid(azb)=ax+byintextended_euclid(inta,intb,int&x,int&y){intd;if(b==0){x=1;y=0;returna;}d=extended_eudid(b,a%b,y,x);y-=a/b*x;returnd;}ModularLinearEquation模线性方程(同余方程)〃如果GCD(a,b)不能整除c,则ax+by=c没有整数解//ax=b(modn)n>0〃上式等价于二元一次方程ax-ny=bvoidmodular_linear_equation(inta,intbzintn)<intdzx,yzxO,gcd;〃可以减少扩展欧几里德溢出的可能gcd=GCD(a,n);if(b%gcd(=0){cout<<"nosolution"<<endl;return;}a/=gcd;b/=gcd;n/=gcd;d=extended_euclid(azn,x,y);if(b%d==0){xO=(x*(b/d))%n;//xO:basicsolutionintans=n;for(inti=0;i<d;i++){ans=(xO+i*(n/d))%n;cout<<ans<<endl;}}elsecout<<"nosolution"<<endl;}ChineseRemainderTheorem中国余数定理//x=b[i](modw[i])zie[1,len-1]//前提条件w[i]>0,且w□中任意两个数互质intchinese_remainder(intb口，intw口，intlen){inti,d,x,y,m,n;ret=0;n=1;for(i=0;i<len;i++)n*=w[i];for(i=0;i<len;i++){m=n/w[i];d=extended_euclid(w[i]zmzx,y);ret=(ret+y*m*b[i])%n;}return(n+ret%n)%n;}//m=r[i](moda[i])//a[i]可以不互素//-1表示无解/*Pku2891StrangeWaytoExpressIntegers假设C三Al(modBl),C三A2(modB2)。☆C=Al+X1B,那么X1B1=A2-Al(modB2)o用扩展欧几里德算法求出XL也就求出C。令B=lcm(Bl,B2),那么上面两条方程就可以被C'三C(modB)代替。迭代直到只剩下一条方程。*/LLchinese_remainder2(){inti,j;if(n==l)returnr[0];LLmzx,apre;x=modular_linear_equation(a[0],r[l]-r[O]za[l]);if(x==-l)return-1;m=x*a[0]+r[O];apre=LCM(a[O]za[l]);for(i=2;i<n;i++){x=modular_linear_equation(aprezr[i]-mza[i]);if(x==-l)retum-1;m=x*apre+m;apre=LCM(apreza[i]);}returnm;}EulerFunction欧拉函数〃求・.n-l中与n互质数的个数inteuler(intn){intans=l;inti;for(i=2;i*i<=n;i++){if(n%i==0){n/=i;ans*=i-1;while(n%i==0){n/=i;ans*=i;}}}if(n>1){ans*=n-1;}returnans;}Farey总数〃求MAX以内所有Farey的总数constintMAX=1000100;intn;boolnum[1100];//sqrt(MAX)intprime[1100],total;—int64f[MAX]zinc[MAX];voidcal_prime(){inti,j;memset(numzfalse,sizeof(num));total=0;for(i=2;i<1100;i++){if(!num[i]){prime[total++]=i;j=i+i;while(j<1100){num[j]=true;j+=i;}}}}voidcal_farey(){inti,j,k;inc[l]=1;for(i=2;i<MAX;i++){for(j=0;j<totaI；j++){if(i%prime[j]==0){k=i/prime[j];if(k%prime[j]==0)inc[i]=inc[k]*prime[j];elseinc[i]=inc[k]*(prime[j]-1);break;}}if(j==total)inc[i]=i-1;}f[l]=0;for(i=2;i<MAX;i++)f[i]=f[i-l]+inc[i];}intmain(){cal_prime();caLfarey();while(scanf("%d"z&n),n){printf("%I64d\n",f[n]);}}Farey序列构造〃构造5000以内的Farey序列constintMAX=8000000;inttotal;intnzk;intfarey[2][MAX];voidmake_farey_seq(intxl,intyljntx2,inty2){if(xl+x2>n11yl+y2>n)return;make_farey_seq(x1,yl,xl+x2,yl+y2);total++;farey[0][total]=xl+x2;farey[l][total]=yl+y2;make_farey_seq(xl+x2zyl+y2,x2,y2);}intmain(){intt;scanf("%d%d"z&nz&t);total=l;farey[0][l]=0;farey[l][l]=1;make_farey_seq(04,1/1)；farey[0][total+1]=l;farey[l][total+l]=1;total++;while(t-){scanf("%d"z&k);if(k>total)puts("NoSolution");elseprintf(,,%d/%d\n"/farey[0][k]zfarey[l][k]);}}Miller_Rabbin素数测试，Pollard_rho因式分解typedef_int64164;constchar*pformat=n%I64d";164big_rand(I64m){164x=rand();x*=rand();if(x<0)x=-x;returnx%=m;}//x*y%n164mod_mul(I64x,164yz164n){if(x==011y==0)return0;return(((x&l)*y)%n+(mod_mul(x>>lzyzn)<<l)%n)%n;}//xAy%n164mod_exp(I64xz164y,164n){164ret=1;while(y){if(y&l)ret=mod_mul(ret,xzn);x=mod_mul(xzxzn);y>>=1;}returnret;}boolMiller_Rabbin(I64n){//O(times*(logN)A3)164i,j,x,m,k;if(n==2)returntrue;if(n<211!(n&l))returnfalse;m=n-1;k=0;while(!(m&l))m>>=1,k++;//binaryscanfor(i=0;i<4;i++){//testtimesx=big_rand(n-2)+2;x=mod_exp(xzm,n);if(x==1)continue;for(j=0;j<k;j++){if(x==n-1)break;x=mod_mul(xzx/n);}if(j>=k)returnfalse;}returntrue;/*lrjP.218for(i=0;i<20;i++){x=big_rand(n-2)+2;if(mod_exp(xzn-lzn)!=1)returnfalse;}returntrue;*/}164gcd(I64x,164y){if(x>y)std::swap(xzy);while(x){164t=y%x;y=x;x=t;}returny;}164func(I64x,164m){return(mod_mul(x,xzm)+l)%m;}164Pollard(I64n){if(Miller_Rabbin(n))returnn;if(!(n&l))return2;164izxzyzret;i=1;while(true){x=i++;y=func(xzn);ret=gcd(y-xzn);while(ret==1){x=func(x,n);y=func(func(yzn)zn);ret=gcd((y-x+n)%n,n)%n;}if(O<ret&&ret<n)returnret;}}164factor[100]znfaczminfac;voidcal_factor(I64n){164x=Pollard(n);if(x==n){//factor[nfac++]=x;minfac=min(minfaczx);return;}cal_factor(x);cal_factor(n/x);}voidprint_factor(I64n){164i;nfac=0;cal_factor(n);std::sort(factorzfactor+nfac);for(i=0;i<nfac;i++){if(i>0)putchar('');printf(pformatzfactor[i]);}puts("");}const164lim=100000;intmain(){164nztJ;srand((unsigned)time(NULL));scanf(pformatz&t);while(t-){scanf(pformatz&n);if(Miller_Rabbin(n))puts("Prime");else{if(!(n&l))puts("2");else{for(minfac=3;minfac<lim&&n%minfac;minfac+=2);if(minfac>=lim){164rn=sqrt(1.0*n);if(rn*rn==n){minfac=rn;cal_factor(rn);}else{minfac=n;cal_factor(n);}}printf(pformatzminfac);puts。);}}}}第五章图论算法.最小生成树(Kruscal算法)FunctionName: 最小生成树(Kruscal算法)Description: ZJU1203SwordfishO(E*LogE)#include<iostream>#include<algorithm>#include<cstdio>#include<cmath>usingnamespacestd;structstruct_edges{intbvztv;//bv起点tv终点doublew;〃权值};struct_edgesedges[10100];〃边集structstruct_a{doublex;doubley;};struct_aarr_xy[101];intpoint[101],n,e;//n顶点数，e边数(注意是无向网络)doublesum;intkruscal_fl(intpoint口，intv){inti=v;while(point[i]>0)i=point[i];returni;}boolUDIesser(struct_edgesa,struct_edgesb){returna.w<b.w;}voidkruscal。〃只需要:准备好n,e,递增的边集edges口即可一使用{intvlzv2,iJ;for(i=0;i<n;i++)point[i]=0;i=j=0；while(j<n-l&&i<e){vl=kruscal_fl(pointzedges[i].bv);v2=kruscal_fl(point,edges[i].tv);if(vl!=v2){sum+=edges[i].w;〃注意sum初始为0point[vl]=v2;j++；}i++；}}intmain(){intkjzj;cin>>n;k=0;while(n!=0){sum=0;k++;for(i=0;i<n;i++)cin>>arr_xy[i].x>>arr_xy[i].y;e=0;for(i=0;i<n;i++)〃从。开始计数for(j=i+l;j<n;j++)〃注意是无向网络{if(i==j)continue;edges[e].bv=i;edges[e].tv=j;edges[e].w=sqrt((arr_xy[i].x-arr_xy[j].x)*(arr_xy[i].x-arr_xy[j].x)+(arr_xy[i].y-arr_xy[j].y)*(arr_xy[i].y-arr_xy[j].y));e++；}sort(edges,edges+e,UDIesser);〃得到•个递增的边集，注意是从。开始计数kruscal();printf("Case#%d:\n,,/k);//cout<<HCase#M<<k«M:"<<endl;printf(nTheminimaldistanceis:%.2f\n",sum);〃输Hlsumcin>>n;if(n!=0)printf("\n");}}.最小生成树(Prim算法)FunctionName: 最小生成树(Prim算法)Description: ZJU1203SwordfishO(NA2)#include<iostream>#include<cmath>#include<cstdio>usingnamespacestd;doublesum,arrJist[101][101],min;inti,j,k=0,n;structstruct_a{floatx；floaty;};struct_aarr_xy[101];structstruct_b{intpoint;floatlowcost;};struct_bclosedge[101];voidprim(intn)//prim需要准备：n顶点数arjlist□□顶点的邻接矩阵也是从。开始计数{inti,j,k;k=O;for(j=0;j<n;j++)<if(j!=k){closedge[j].point=k;closedge[j].lowcost=arr_list[k][j];}}closedge[k].lowcost=0;for(i=0;i<n;i++){min=10000;forQ=0;j<n;j++){if(closedge[j].lowcost!=0&&closedgefj].lowcost<min){k=j;min=closedge[j].lowcost;}}sum+=closedge[k].lowcost;〃不要改成sum+=min;sum即为所求值closedge[k].Iowcost=0;for(j=0；j<n；j++){if(arr_list[k][j]<closedge[j].lowcost){closedge[j].point=k;closedge[j].lowcost=arr_list[k][j];}}}}/*arr_list[][]=Wij如果Vi,Vj有边0如果i=j无限大如果没有边*/intmain(){cin>>n;while(n!=0){sum=0;k++;for(i=0;i<n;i++)cin>>arr_xy[i].x>>arr^xy[i].y;for(i=0;i<n;i++)for(j=0;j<n;j++)〃得到邻接矩阵arr_list[][]arr_list[i][j]=a「r_list[j][i]=sqrt((arr_xy[i]・x-arr_xy[j].x)*(arr_xy[i].x-arr_xy[j].x)4-(arr_xy[i].y-arr_xy[j].y)*(arr_xy[i].y-arr_xy[j].y));prim(n);cout<<"Case#"<<k<<":"<<endl;printf("Theminimaldistanceis:%,2f\n”,sum);cin>>n;if(n!=O)printf("\n");}}.单源最短路径(Bellman-ford算法)structnode{inte,v;node(inta=Ozintb=0):e(a),v(b){)};vector<vector<node>>path;intn,p,q;intdist[1000100];/*SPFA(ShortestPathFasterAlgorithm)Bellman-Ford算法的一种队列实现，减少了不必要的冗余计算返回值为false,说明队列不为空，存在负权环*/boolSPFA(){intiJ,kznowzl;nodenext;bitset<1000100>vis;queue<int>SQ;memset(dist,-l/Sizeof(dist));SQ.push(l);vis[l]=true;dist[l]=0;for(i=0;i<=n;i4-+){I=SQ.size();if(I==0)break;while(I-){now=SQ.front();SQ.pop();vis[now]=false;for(j=path[now].size()-l;j>=O;j—){next=path[now][j];if(dist[next.e]==-l11dist[next.e]>dist[now]+next.v){dist[next.e]=dist[now]+next.v;if(!vis[next.e]){SQ.push(next.e);vis[next.e]=true;}}}}}returnSQ.empty();}4.单源最短路径(Dijkstra算法)FunctionName: 单源最短路径(Dijkstra算法)Description: 贪心，O(N人2),不能有负权intmatrix[200][200]zn; //matrix[][],30000表小无限大，即无边.否则为仃边,其值为边的权值voidDijkstra(intxjnty)〃起点Vx终点Vy{intizjzk,path[40000]zmark[40000];intmin,dist[40000];for(i=l;i<=n;i++){mark[i]=O;dist[i]=matrix[x][i];path[i]=x;}mark[x]=1;do{min=30000;k=0;for(i=l;i<=n;i++)if(mark[i]==0&&dist[i]<min){min=dist[i];k=i；?if(k){mark[k]=1;for(i=l;i<=n;i+4-)if(matrix[k][i]<30000&&min+matrix[k][i]<dist[i]){dist[i]=min+matrix[k][i];path[i]=k;})}while(k);cout<<dist[y]<<endl;//dist[y]的值就是从Vx到Vy的最短路径值〃如果希望得到路径，加入如下代码：do{cout<<k<<n<—n;k=path[k];}while(k!=x);cout<<x<<endl;}5.全源最短路径(Folyd算法)FunctionName: 全源最短路径(Folyd算法)Description: DPZO(NA3)〃初始化//path[i][j]=j;voidFloyd(){inti,j,k;for(k=0;k<vertex_number;k++){for(i=0;i<vertex_number;i++)<for(j=0;j<vertex_number;j++){if((graph[i][k]==-l)||(graph[k][j]==-l))continue;if((graph[i][j]==-l)||(graph[i][j]>graph[i][k]+graph[k][j])){graph[i][j]=graph[i][k]+graph[k][j]; /*最短路径值*/path[i][j]=k; /*最短路径*/}}}}}6.拓扑排序*FunctionName: 拓扑排序//degree[] 每个结点的入度//f[] 每个结点所在的层voidToplogical_sort(){intiJ;boolp=true;top=0;while(p){p=false;top++;for(i=l;i<=n;i++)if(degree[i]==O){p=true;f[i]=top;}for(i=l;i<=n;i++)if(f[i]==top){for(j=l;j<=n;j++)if(map[i][j])degree[j]-;degree[i]="l;} }top-;}7.网络预流和最大流/*网络中求最大流Edmonds_Karp最短增广路算法。(VE八2)参数含义：n代表网络中节点数，第0节点为源点，第n节点为汇点net口口代表剩余网络,0表示无通路path□保存增广路径neck口代表瓶颈，保存增广路径最小容量返回值：最大流量*/constintNMAX=210;intnet[NMAX][NMAX];intpath[NMAX],n;intbfs(){queue<int>SQ;intneck[NMAX],i;memset(path,-l,sizeof(path));neck[O]=INT_MAX;SQ.push(l);while(!SQ.empty()){intnow=SQ.front();SQ.pop();if(now==n)break;for(i=l;i<=n;i+4-){if(net[now][i]>0&&path[i]==-1){path[i]=now;neck[i]=min(neck[now]znet[now][i]);SQ.push(i);}}}if(path[n]==-1)return-1;returnneck[n];}intEdmonds_Karp(){intnow,step;intmax_flow=0;while((step=bfs())!=-1){max_flow+=step;now=n;while(now!=-1){intpre=path[now];net[pre][now]-=step;net[now][pre]+=step;now=pre;}}returnmax_flow;}/*网络中求最大流HLPP高度标号预流推进算法0(V人2*E^0.5)参数含义：n代表网络中节点数，第0节点为源点，第n节点为汇点net口口代表剩余网络,0表示无通路earn□代表各点的盈余high口代表各点的高度返回值： 最大流量*/constintNMAX=110;intearn[NMAX]znet[NMAX][NMAX]zhigh[NMAX];intn,m;queue<int>SQ;voidpush(intu,intv){intex=min(earn[u]znet[u][v]);earn[u]-=ex;net[u][v]-=ex;earn[v]+=ex;net[v][u]+=ex;}voidrelable(intu){intmmin=INT_MAX;for(i=0;i<=n;i++){if(net[u][i]>0&&high[i]>=high[u]){mmin=min(mmin,high[i]);}}high[u]=mmin+1;}voiddischarge(intu){inti,vn;while(eam[u]>0){vn=0;for(i=0;i<=n&&earn[u]>0;i++){if(net[u][i]>0&&high[u]==high[i]+l){push(uj);vn++;if(i!=n)SQ.push(i);}>if(vn==0)relable(u);}>voidinit_preflow(){inti;memset(highzOzsizeof(high));memset(earnzOzsizeof(earn));while(!SQ.empty())SQ.pop();high[O]=n+l;for(i=l;i<=n;i4-+){if(net[O][i]>0){earn[i]=net[0][i];earn[0]-=net[0][i];net[i][0]=net[0][i];net[0][i]=0;if(i!=n)SQ.push(i);}}}inthigh_label_preflow_push(){intij；init_preflow();while(!SQ.empty()){intoverp=SQ.front();SQ.pop();discharge(overp);}returnearn[n];}/*网络中求最大流Dinic算法O(V人2E)适用于稠密图，实际复杂度低于HLPP模板参数含义：n代表网络中节点数，第节点为源点，第n节点为汇点net代表网络，使用前向星表示法存储边dis口代表从源点出发的距离标号path□代表模拟栈中的路径信息cur□代表模拟栈的现场保存返回值：最大流量*/constintNMAX=21000;constintMMAX=250000<<l;structEDGE{intu,v,cap,flow;intnext;EDGE(int_u=0,int_v=0zint_c=0zint_f=0):u(_u)zv(_v),cap(_c)zflow(_f){}};constintENDFLAG=-1;structEDGEUST{intstart[NMAX];intlast[NMAX];inttot;EDGEarc[MMAX];voidclear(){tot=ENDFLAG+l;memset(lastzENDFLAG,sizeof(last));}voidpush_back(EDGEedge){edge.next=ENDFLAG;arc[tot]=edge;if(last[edge.u]!=ENDFLAG)arc[last[edge.u]].next=tot;elsestart[edge.u]=tot;last[edge.u]=tot;tot++;}〃创建双向弧voidadd_arc(EDGEedge){push_back(edge);push_back(EDGE(edge.vzedge.uzedge.cap));}}net;intque[2][NMAX];intqf[2]zqe[2]zqnow;#definepush_que(a)(que[qnow][qe[qnow]