上海交通大學ACM算法模板

ACM算法模板集Contents.常用函數(shù)與STL.重要公式與定理FibonacciNumberLucasNumberCatalanNumberStirlingNumber（SecondKind）BellNumberStirling'sApproximationSumofReciprocalApproximationYoungTableau整數(shù)劃分錯排公式三角形內(nèi)切圓半徑公式三角形外接圓半徑公式圓內(nèi)接四邊形面積公式基礎(chǔ)數(shù)論公式.大數(shù)模板，字符讀入.數(shù)論算法GreatestCommonDivisor最大公約數(shù)Prime素數(shù)判斷SievePrime素數(shù)篩法ModuleInverse模逆元ExtendedEuclid擴展歐幾里德算法ModularLinearEquation模線性方程（同余方程）ChineseRemainderTheorem中國余數(shù)定理（互素于非互素）EulerFunction歐拉函數(shù)Farey總數(shù)Farey序列構(gòu)造Miller_Rabbin素數(shù)測試，Pollard_rho因式分解五.圖論算法.最小生成樹（Kruscal算法）.最小生成樹（Prim算法）.單源最短路徑（Bellman-ford算法）.單源最短路徑（Dijkstra算法）.全源最短路徑（Folyd算法）.拓撲排序.網(wǎng)絡(luò)預流和最大流.網(wǎng)絡(luò)最小費用最大流.網(wǎng)絡(luò)最大流（高度標號預流推進）.最大團.二分圖最大匹配（匈牙利算法）.帶權(quán)二分圖最優(yōu)匹配（KM算法）.強連通分量（Kosaraju算法）.強連通分量（Gabow算法）.無向圖割邊割點和雙連通分量.最小樹形圖0（N人3）.最小樹形圖O（VE）六.幾何算法.幾何模板.球面上兩點最短距離.三點求圓心坐標.三角形幾個重要的點七.專題討論.樹狀數(shù)組.字典樹.后綴樹.線段樹.并查集.二叉堆.逆序數(shù)（歸并排序）.樹狀DP.歐拉路.八數(shù)碼.高斯消元法.字符串匹配（KMP算法）.全排列，全組合.二維線段樹.穩(wěn)定婚姻匹配.后綴數(shù)組.左偏樹.標準RMQ-ST.度限制最小生成樹.最優(yōu)比率生成樹（0/1分數(shù)規(guī)戈I）.最小花費置換.區(qū)間K大數(shù).LCA-RMQ-ST.LCA-larjan.指數(shù)型母函數(shù).指數(shù)型母函數(shù)(大數(shù)據(jù)).單詞前綴樹(字典樹+KMP).FFT(大數(shù)乘法).二分圖網(wǎng)絡(luò)最大流最小割.混合圖歐拉回路.無源匯上下界網(wǎng)絡(luò)流.二分圖最小點權(quán)覆蓋.帶約束的軌道計數(shù)(Burnside引理).三分法求函數(shù)波峰.單詞計數(shù)，矩陣乘法.字符串和數(shù)值hash.滾動隊列，前向星表示法.最小點基，最小權(quán)點基第一章常用函數(shù)和STL一.常用函數(shù)#include<stdio.h>intgetchar(void); 〃讀取一個字符/一般用來去押無用字箱char*gets(char*str); 〃讀取一行字符串#include<stdlib.h>void*malloc(size_tsize); 〃動態(tài)內(nèi)存分配，開辟大小為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的對數(shù)，基數(shù)為edoublelog(doublenum);〃求num的根

doublesqrt(doublenum);〃求base的exp次方doublepow(doublebase,doubleexp);#include<string.h>〃初始化內(nèi)存，常用來初始化數(shù)組void*memset(void*buffer;intchzsize_tcount);memset(the_arrayz0,sizeof(the_array));〃printf是它的變形，常用來將數(shù)據(jù)格式化為字符串intsprintf(char*buffer;constchar"format,...);sprintf(s,"%d%d"/123z4567);//s=n1234567n〃scanf是它的變形，常用來從字符串中提取數(shù)據(jù)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()優(yōu)先隊列，empty(),top(),pop(),push()集合關(guān)聯(lián)數(shù)組，常用來作hash映射[標準algorithm摘錄]for_each()find()replace()copy()remove()reverse()sort()partial_sort()binary_search()merge()對每一個元素都喚起(調(diào)用)一個函數(shù)查找第一個能與引數(shù)匹配的元素用新的值替換元素，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個三角形的不同切割數(shù)n+1個數(shù)相乘，給每兩個元素加上括號的不同方法數(shù)Sample:n=2;(1(23)),((12)3)n=3；(1(2(34))),(1((23)4)),((12)(34)),((1(23))4),(((12)3)4)n個節(jié)點的不同形狀的二叉樹數(shù)(嚴《數(shù)據(jù)結(jié)構(gòu)》P.155)4)從n*n方格的左上角移動到右下角不升路徑數(shù)Sample:StirlingNumber(SecondKind)S(n,m)表示含n個元素的集合劃分為m個集合的情況數(shù)或者是n個有標號的球放到m個無標號的盒子中，要求無一為空，其不同的方案數(shù)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個元素集合所有的劃分數(shù)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個數(shù)所組成的楊式圖表的個數(shù)Formula:Y[l]=1;Y[2]=2;Y(n]=Y[n-1]+(n-1)*Y[n-2];(n>2).整數(shù)劃分將整數(shù)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)若分解出來的每個數(shù)均有一個上限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]);.三角形內(nèi)切圓半徑公式2Sr= ；a+b+cp=(a+b+c)/2;S=Vp(p-a)(p-b)(p-c);.三角形外接圓半徑公式abcR=k.圓內(nèi)接四邊形面積公式a+b*c+dP=——2 ；S=V(p-a)(p-b)(p-c)(p-d);.基礎(chǔ)數(shù)論公式1)模取募an%b=((((a*b)*a)%b)...)%b;n的約數(shù)的個數(shù)n= *32^*33^*.?.*31nll若n滿足 ,則n的約數(shù)的個數(shù)為(ill+1)(112+1)(113+1)...(inn+1);第三章大數(shù)模板typedefinthugeint;〃應(yīng)不大于，以防乘法時溢出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];〃可以控制人數(shù)的位數(shù)intlen;〃大數(shù)長度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;〃位數(shù)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];}}〃讀取整數(shù)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;}〃帶負數(shù)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;}〃讀取整數(shù)，可判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;}〃讀取浮點數(shù)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;}第四章數(shù)論算法GreatestCommonDiviso「最大公約數(shù)intGCD(intx,inty){intt;while(y>0){t=x%y;x=y;y=t;}returnx;}Prime素數(shù)判斷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素數(shù)篩法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沒有整數(shù)解//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中國余數(shù)定理//x=b[i](modw[i])zie[1,len-1]//前提條件w[i]>0,且w□中任意兩個數(shù)互質(zhì)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假設(shè)C三Al(modBl),C三A2(modB2)?！頒=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歐拉函數(shù)〃求?.n-l中與n互質(zhì)數(shù)的個數(shù)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總數(shù)〃求MAX以內(nèi)所有Farey的總數(shù)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序列構(gòu)造〃構(gòu)造5000以內(nèi)的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素數(shù)測試，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;〃權(quán)值};struct_edgesedges[10100];〃邊集structstruct_a{doublex;doubley;};struct_aarr_xy[101];intpoint[101],n,e;//n頂點數(shù)，e邊數(shù)(注意是無向網(wǎng)絡(luò))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++)〃從。開始計數(shù)for(j=i+l;j<n;j++)〃注意是無向網(wǎng)絡(luò){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);〃得到?個遞增的邊集，注意是從。開始計數(shù)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頂點數(shù)arjlist□□頂點的鄰接矩陣也是從。開始計數(shù){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算法的一種隊列實現(xiàn)，減少了不必要的冗余計算返回值為false,說明隊列不為空，存在負權(quán)環(huán)*/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),不能有負權(quán)intmatrix[200][200]zn; //matrix[][],30000表小無限大，即無邊.否則為仃邊,其值為邊的權(quán)值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[] 每個結(jié)點的入度//f[] 每個結(jié)點所在的層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.網(wǎng)絡(luò)預流和最大流/*網(wǎng)絡(luò)中求最大流Edmonds_Karp最短增廣路算法。(VE八2)參數(shù)含義：n代表網(wǎng)絡(luò)中節(jié)點數(shù)，第0節(jié)點為源點，第n節(jié)點為匯點net口口代表剩余網(wǎng)絡(luò),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;}/*網(wǎng)絡(luò)中求最大流HLPP高度標號預流推進算法0(V人2*E^0.5)參數(shù)含義：n代表網(wǎng)絡(luò)中節(jié)點數(shù)，第0節(jié)點為源點，第n節(jié)點為匯點net口口代表剩余網(wǎng)絡(luò),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];}/*網(wǎng)絡(luò)中求最大流Dinic算法O(V人2E)適用于稠密圖，實際復雜度低于HLPP模板參數(shù)含義：n代表網(wǎng)絡(luò)中節(jié)點數(shù)，第節(jié)點為源點，第n節(jié)點為匯點net代表網(wǎng)絡(luò)，使用前向星表示法存儲邊dis口代表從源點出發(fā)的距離標號path□代表模擬棧中的路徑信息cur□代表模擬棧的現(xiàn)場保存返回值：最大流量*/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++;}〃創(chuàng)建雙向弧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]