ACM程序設(shè)計(jì)大賽常用算法模板

ACM算法模板總結(jié)班級(jí):計(jì)算機(jī)091學(xué)號(hào):10921018姓名:鮑杭文件狀態(tài)：[√]草稿[]正式發(fā)布[]正在修改文件標(biāo)識(shí)：ACM算法模板總結(jié)當(dāng)前版本：1.0作者：鮑杭編完成日期：2023-4-3目錄數(shù)論 1高精度算法[1] 1高精度加法 2高精度減法 2高精度乘法 4整型常量階乘 6整型常量階乘和 6高精度的乘方 7高精度除法 7帶符號(hào)的數(shù)據(jù)運(yùn)算 9廣度優(yōu)先搜索大數(shù)應(yīng)用 11基于比擬的排序算法 12插入排序 12選擇排序 13冒泡排序 13堆排序 13歸并排序 14快速排序 15希爾排序 16同余運(yùn)算 16模線性方程問(wèn)題 16計(jì)算a^nmodk 19階乘最后非0位 20素?cái)?shù)篇 20線性篩法 21費(fèi)馬小定理 22MR素性測(cè)試 22歐拉函數(shù)問(wèn)題 22巴赫猜測(cè) 23最大公約數(shù) 24最小公倍數(shù) 25不定方程求解 25概率因子分解Pollard算法 25數(shù)值計(jì)算[2] 26定積分計(jì)算(Romberg) 26多項(xiàng)式求根(牛頓法) 27周期性方程(追趕法) 29組合論[3] 30組合公式 30全組合排列 30非重復(fù)組合排列 32類循環(huán)組合排列 34普通選擇性組合排列 35生成全子集組合排列 36非重復(fù)生成全子集組合排列 37一般組合 39排列組合生成 39生成gray碼 41置換(polya) 42字典序全排列 42字典序組合 43計(jì)算幾何 43對(duì)于任意多邊形求面積 43判斷兩線是否相交 44二分查找模板 44二分圖匹配模板 45動(dòng)態(tài)規(guī)劃 46求局部最大和模板 46字符串 46字符計(jì)數(shù)應(yīng)用 46最大子序列算法 47求最長(zhǎng)公供子串〔DP算法〕 48數(shù)據(jù)結(jié)構(gòu) 49圖論 49入度和出度表的轉(zhuǎn)化 49生成樹 52最小生成樹 56關(guān)鍵路徑 59迷宮算法的隊(duì)列實(shí)現(xiàn) 64最短路徑 67棧的相關(guān)操作 75一元多項(xiàng)式計(jì)算 78單鏈表的簡(jiǎn)單操作 84快速排序 89哈夫曼編碼 90隊(duì)列的簡(jiǎn)單操作 94KMP模式匹配算法 98常用的數(shù)學(xué)公式[4] 100中國(guó)剩余定理 100根本幾何公式 100歐拉公式 101劃分問(wèn)題： 102Stirling公式 102皮克定理 103卡特蘭數(shù) 103原理: 103錯(cuò)排公式 103等比數(shù)列 104等差數(shù)列 104二次函數(shù) 104二次方程 105約瑟夫環(huán) 105多邊形面積 105均值不等式的簡(jiǎn)介 105均值不等式的變形 106Lucas定理 107斐波那契數(shù)列 107歐拉函數(shù) 108螞蟻爬繩 109(a/b)%m 109泰勒公式 109乘法與因式分解公式 109三角不等式 110某些數(shù)列的前n項(xiàng)和 110二項(xiàng)式展開公式 110三角函數(shù)公式 110常用系統(tǒng)函數(shù) 112將字符串轉(zhuǎn)化為數(shù)字 112系統(tǒng)函數(shù)排序 112數(shù)論高精度算法[1]#include<stdio.h>#include<string.h>charc[2000];//全局變量，存儲(chǔ)大數(shù)運(yùn)算的結(jié)果chararr[1000];//高精度除以高精度的余數(shù)longz=0;//高精度除以低精度的余數(shù)intJudge(charch[]){//判斷字符串ch是否全為0，假設(shè)全為0，返回0，否那么返回1inti,k; k=strlen(ch); for(i=0;i<k;i++) if(ch[i]!='0') return0; return1;}intCompare(chara[],charb[]){//比擬字符串的大小，方法不同于strcmp函數(shù)，類似于整型常量的比擬 intlena,lenb,i; lena=strlen(a); lenb=strlen(b); if(lena<lenb) return-1; elseif(lena>lenb) return1; else { if(strcmp(a,b)==0) return0; else { for(i=0;i<lena;i++) { if(a[i]>b[i]) return1; if(a[i]<b[i]) return-1; } return0; } }}高精度加法/*算法：先確定a和b中的最大位數(shù)k，然后依照由低至高位的順序進(jìn)行加法運(yùn)算。注意進(jìn)位，假設(shè)高位有進(jìn)位，那么c的長(zhǎng)度為k+1。*/voidBigNumberAdd(chara1[],charb1[]){ inti,j,k,lena,lenb; inta[1000]={0},b[1000]={0},d[1000]={0}; lena=strlen(a1); lenb=strlen(b1); //將加數(shù)與被加數(shù)化為整型數(shù)組，并且該數(shù)組的其他位為 for(i=0;i<lena;i++) a[i]=a1[lena-i-1]-'0'; for(i=0;i<lenb;i++) b[i]=b1[lenb-1-i]-'0'; //當(dāng)數(shù)組除了加數(shù)和被加數(shù)以外的整型數(shù)組元素均為0時(shí)，無(wú)需考慮lena和lenb的大小 k=lena>lenb?lena:lenb; for(i=0;i<k;i++) { d[i]=a[i]+b[i]+d[i]; d[i+1]=d[i+1]+d[i]/10; d[i]=d[i]%10; } //假設(shè)高位進(jìn) while(d[k]) k++; while(!d[k-1]) k--;//001+0003=4 //將整型數(shù)組逆著轉(zhuǎn)變并賦值給c字符型數(shù)組 for(j=0;j<k;j++) c[j]=d[k-j-1]+'0'; if(Judge(c))//假設(shè)全為0，那么只輸出一個(gè) strcpy(c,"0");}高精度減法/*算法：依照由低位至高位的順序進(jìn)行減法運(yùn)算。在每次位運(yùn)算中，假設(shè)出現(xiàn)不夠減的情況，那么向高位借位。在進(jìn)行了la的減法后，假設(shè)最高位為0，那么a的長(zhǎng)度減。假設(shè)A、B大小未知，那么需先判斷大小。*/voidBigNumberSub(chara1[],charb1[]){//a1為被減數(shù)，b1為減數(shù) intlena,lenb,i,j,k,flag; inta[1000]={0},b[1000]={0},d[1000]={0}; lena=strlen(a1); lenb=strlen(b1); if(Compare(a1,b1)>=0) {//假設(shè)被減數(shù)大于等于減數(shù) for(i=0;i<lena;i++) a[i]=a1[lena-1-i]-'0'; for(i=0;i<lenb;i++) b[i]=b1[lenb-1-i]-'0'; flag=0;//結(jié)果正的標(biāo)志 } else {//假設(shè)被減數(shù)小于減數(shù) for(i=0;i<lenb;i++) a[i]=b1[lenb-1-i]-'0'; for(i=0;i<lena;i++) b[i]=a1[lena-1-i]-'0'; flag=1;//結(jié)果負(fù)的標(biāo)志 } k=lena>lenb?lena:lenb; for(i=0;i<k;i++) {//大數(shù)減小數(shù) if(a[i]<b[i]) {//假設(shè)被減數(shù)不夠減，向高位借一位 a[i+1]--; d[i]=a[i]-b[i]+10; } else d[i]=a[i]-b[i]; } //假設(shè)較高位已為0，并且不止1位時(shí) while(!d[i-1]) { k--; i--; } //根據(jù)flag，輸出有無(wú)"-" if(!flag) { for(i=0;i<k;i++) {//將結(jié)果轉(zhuǎn)化為字符逆著賦給數(shù)組c if(!i&&!d[k-i-1])//假設(shè)差的第一個(gè)字母為0，那么馬上跳過(guò) continue; c[i]=d[k-i-1]+'0'; } } else { c[0]='-'; for(i=1;i<=k;i++) {//將結(jié)果轉(zhuǎn)化為字符逆著賦給數(shù)組c if(i==1&&!d[k-i])//假設(shè)差的第一個(gè)字母為0，那么馬上跳過(guò) continue; c[i]=d[k-i]+'0';//注意d的下標(biāo)，不是k-i-1 } } if(Judge(c))//假設(shè)差全為0，那么只輸出一個(gè) strcpy(c,"0");}高精度乘法高精度乘以低精度/*算法：將多位數(shù)存入數(shù)組，低位在前、高位在后，然后用一位數(shù)去乘數(shù)組的各位，考慮進(jìn)位，最后按正常順序輸出*/voidBigNumMultiSmall(chara1[],intb1){ inti,j,t; inta[2000]={0}; //將字符串轉(zhuǎn)化為整型數(shù)組，并逆置 t=strlen(a1); for(i=0;i<t;i++) a[i]=a1[t-1-i]-'0'; //整型數(shù)組的每個(gè)元素乘以b1，然后對(duì)其進(jìn)行求余，整除，使其只有一位數(shù) a[0]=a[0]*b1; for(i=1;i<t;i++) { a[i]*=b1; a[i]+=a[i-1]/10; a[i-1]=a[i-1]%10; } while(a[i-1]>9) {//假設(shè)最后一個(gè)元素大于9 a[i]=a[i-1]/10; a[i-1]=a[i-1]%10; i++; } //將得到的整型數(shù)組逆置賦給字符串 for(j=0;j<i;j++) c[j]=a[i-j-1]+'0'; if(Judge(c))//假設(shè)積全為0，那么只輸出一個(gè)0 strcpy(c,"0");}高精度乘以高精度voidBigNumMultiBig(chara1[],charb1[]){ inti,j,k,lena,lenb; inta[1000]={0},b[1000]={0},d[2000]={0}; //將字符串轉(zhuǎn)化為整型數(shù)組，并逆置 lena=strlen(a1); lenb=strlen(b1); for(i=0;i<lena;i++) a[i]=a1[lena-i-1]-'0'; for(i=0;i<lenb;i++) b[i]=b1[lenb-i-1]-'0'; //計(jì)算乘數(shù)從低位到高位以此乘以被乘數(shù)的低位到高位 for(i=0;i<lena;i++) for(j=0;j<lenb;j++) { d[i+j]=d[i+j]+a[i]*b[j]; d[i+j+1]+=d[i+j]/10; d[i+j]=d[i+j]%10; } //根據(jù)高位是否為判斷整型數(shù)組的位數(shù) k=lena+lenb; while(!d[k-1]) k--; //積轉(zhuǎn)化為字符型 for(i=0;i<k;i++) c[i]=d[k-1-i]+'0'; if(Judge(c))//假設(shè)積全為0，那么只輸出一個(gè)1 strcpy(c,"0");}整型常量階乘voidBigNumFact(intx){ inti,k,m=0,a[1000]={0}; a[0]=1; for(;x;x--) {//m為在求階乘過(guò)程中a的元素個(gè)數(shù) for(k=i=0;i<=m;i++) { k=k+a[i]*x;//數(shù)組各個(gè)元素均乘以x(x遞減)，以完成階乘的運(yùn)算 a[i]=k%10; k/=10; } while(k) { a[++m]=k%10; k/=10; } } //階乘的結(jié)果轉(zhuǎn)化為字符型 for(i=0;i<=m;i++) c[i]=a[m-i]+'0'; if(Judge(c))//假設(shè)結(jié)果全為，那么只輸出一個(gè) strcpy(c,"0");}整型常量階乘和voidBigNumFactAdd(intt)//可以改良，減少算法時(shí)間復(fù)雜度{ inti; charsum[2000],d[2000]; //對(duì)字符串進(jìn)行初始化 memset(d,0,sizeof(d)); memset(sum,0,sizeof(sum)); //分別求出相應(yīng)i的階乘然后相加 for(i=t;i>0;i--) { BigNumFact(i);//調(diào)用大數(shù)乘法?？梢詼p少時(shí)間復(fù)雜度 strcpy(d,c); memset(c,0,sizeof(c)); BigNumberAdd(d,sum); strcpy(sum,c); memset(c,0,sizeof(c)); } strcpy(c,sum);//將結(jié)果賦值給全局變量，進(jìn)行輸出}高精度的乘方voidBigNumInvol(chara1[],intb1)//冪為整型常量{ inti; chartemp[1000]; strcpy(temp,a1);//注意乘方是自己乘自己，而不是結(jié)果乘結(jié)果 for(i=2;i<b1;i++) { BigNumMultiBig(a1,temp); strcpy(temp,c); memset(c,0,sizeof(c));//將c清空，防止出現(xiàn)錯(cuò)誤 } //進(jìn)行最后一次乘法 BigNumMultiBig(a1,temp); if(Judge(c))//假設(shè)結(jié)果全為0，那么只輸出一個(gè)0 strcpy(c,"0");}高精度除法高精度除以低精度，只產(chǎn)生余數(shù)intBigNumDividSmall(chara1[],intb1){ if(!b1) return0; inti,j,k,flag=0,a[1000]={0}; charb[2000]; memset(b,0,sizeof(b)); k=strlen(a1); for(i=0;i<k;i++) a[i]=a1[i]-'0'; z=0; for(i=0;i<k;i++) { z=a[i]+z*10; b[i]=z/b1+'0'; z=z%b1; } i=j=0; while(b[i++]=='0'); for(i=i-1;i<k;i++) c[j++]=b[i]; return1;}高精度除以高精度，只產(chǎn)生余數(shù)voidBigNumDividBig(chara1[],charb1[]){ chara[1000],b[1000],time[1000]; intlena1,lentime,i,j,k,flag=0; memset(arr,0,sizeof(arr)); //假設(shè)被除數(shù)小于除數(shù)，那么商為，余數(shù)為被除數(shù) if(Compare(a1,b1)<0) strcpy(arr,a1); //假設(shè)兩數(shù)相等，那么商為，余數(shù)為 elseif(!Compare(a1,b1)) c[0]='1'; //假設(shè)被除數(shù)大于除數(shù) else { j=lentime=0; lena1=strlen(a1); memset(b,0,sizeof(b)); memset(time,0,sizeof(time)); for(i=0;i<lena1;i++) {//計(jì)算得到被除數(shù)的前幾位,得到整型數(shù)組形式的商 //time的一個(gè)元素表示一次相除的商 b[j++]=a1[i]; flag=0; while(Compare(b,b1)>=0) { BigNumberSub(b,b1); strcpy(b,c); memset(c,0,sizeof(c)); time[lentime]++; flag=1;//控制time的元素的位置 } if(flag)//將商轉(zhuǎn)換為字符 time[lentime]+='0'; else//當(dāng)被除數(shù)前幾位小于除數(shù)，商補(bǔ) time[lentime]='0'; if(!strcmp(b,"0"))//假設(shè)b為‘’ j=0; else//繼續(xù)在b的后面加值 j=strlen(b); lentime++; } k=0; for(i=0;i<lentime;i++) if(time[i]!='0') break;//找到time數(shù)組中第一個(gè)不為的位置 for(j=i;j<lentime;j++) c[k++]=time[j]; strcpy(arr,b); } if(Judge(c)) strcpy(c,"0"); if(Judge(arr)) strcpy(arr,"0");}帶符號(hào)的數(shù)據(jù)運(yùn)算2

$1,234,567.89

$9,876,543.21#include<string.h>#include<stdio.h>intmain(){ chars[10001][30],t[30]; longa,sum; inti,j,k,m,n; while(scanf("%d",&n)&&n) { sum=0; getchar(); for(i=0;i<n;i++) { gets(s[i]); m=strlen(s[i]); a=0; for(j=1;j<m;j++) { if(s[i][j]!=','&&s[i][j]!='.') a=a*10+(s[i][j]-'0'); } sum+=a; } if(sum<100) { t[0]=(sum%10-0)+'0'; t[1]=((sum%100-sum%10)/10+'0'); t[2]='.'; t[3]='0'; j=4; } else { t[0]=(sum%10-0)+'0'; t[1]=((sum%100-sum%10)/10+'0'); sum/=100; t[2]='.'; k=0; j=3; while(sum) { if(k!=3) { t[j]=sum%10+'0'; sum/=10; j++; k++; } else { t[j]=','; k=0; j++; } } } printf("$"); for(i=j-1;i>=0;i--) printf("%c",t[i]); printf("\n"); }}廣度優(yōu)先搜索大數(shù)應(yīng)用/*****求一個(gè)數(shù)m它的各個(gè)數(shù)位只由0或1構(gòu)成，并且能被輸入的整數(shù)m整除*******/#include<stdio.h>structnode{ inta,b;///a存0、1,b存余數(shù) intpre;//前一點(diǎn)}queue[200];voidoutput(intk){ if(queue[k].pre>=0) { output(queue[k].pre); } printf("%d",queue[k].a);}intmain(){ intn,r,i,j,L; queue[0].a=1; queue[0].b=1; queue[0].pre=-1; while(scanf("%d",&n)!=EOF)//除數(shù) { if(n==0) return0; charused[200]={0}; used[1]=1; L=1;//r if(n>1) { for(i=0;i<L;i++) { for(j=0;j<2;j++)//確定只有0或1,廣度優(yōu)先搜索思維 { r=(queue[i].b*10+j)%n; if(!used[r]) { queue[L].a=j; queue[L].b=r;//用余數(shù)繼續(xù)乘10+0或+1循環(huán)乘、取余直到整除 queue[L].pre=i; used[r]=1; L++;//用來(lái)控制輸出01序列的,構(gòu)造是從右往左,輸出時(shí)從左往右(L-1開始) } if(r==0) break; } if(r==0) break; } } output(L-1); printf("\n"); } return0;}基于比擬的排序算法#include<iostream>usingnamespacestd;#defineSWAP(i,j){intt=(i);(i)=(j);(j)=t;}插入排序voidInsertSort(int*a,intlen)//算法主體函數(shù){ for(inti=1;i<len;i++) { intj=i,x=a[i]; while(j&&a[j-1]>x) a[j]=a[j-1],j--; a[j]=x; }}/********************************/選擇排序voidSelectSort(int*a,intlen)//算法主體函數(shù){ for(inti=1,j,k;i<len;i++) { for(j=i,k=i-1;j<len;j++) if(a[j]<a[k]) k=j; if(k>=i) SWAP(a[i-1],a[k]); }}/********************************/冒泡排序voidBubbletSort(int*a,intlen)//算法主體函數(shù){ for(boolbSwap=true;bSwap;len--) { bSwap=false; for(intj=1;j<len;j++) if(a[j-1]>a[j]) { SWAP(a[j-1],a[j]); bSwap=true; } }}/********************************/堆排序//堆調(diào)整voidHeapAdjust(int*a,introot,intlen){ intchild,x=a[root]; while(child=root<<1|1,child<len) { if(child<len-1&&a[child]<a[child+1]) child++; if(x<a[child]) { a[root]=a[child]; root=child; } else break; } a[root]=x;}//堆排序voidHeapSort(int*a,intlen)//算法主體函數(shù){ for(inti=len/2-1;i>=0;i--) HeapAdjust(a,i,len); while(--len) { SWAP(a[0],a[len]); HeapAdjust(a,0,len); }}/********************************/歸并排序//歸并voidMerge(int*a,intlen1,intlen2){ int*a1=newint[len1+1],*a2=newint[len2+1],len=len1+len2; for(inti=0;i<len1;i++) a1[i]=a[i]; for(inti=0;i<len2;i++) a2[i]=a[len1+i]; a1[len1]=a2[len2]=INT_MAX; for(inti=0,j=0,k=0;k<len;k++) if(a1[i]<a2[j]) a[k]=a1[i++]; else a[k]=a2[j++]; delete[]a1;delete[]a2;}//歸并排序voidMergeSort(int*a,intlen)//算法主體函數(shù){ if(len>1) { intc=len/2; MergeSort(a,c); MergeSort(a+c,len-c); Merge(a,c,len-c); }}/********************************/快速排序//劃分intPartition(int*a,intlen){ intx=a[--len],i=-1; for(intj=0;j<len;j++) if(a[j]<x) { i++; SWAP(a[i],a[j]); } SWAP(a[i+1],a[len]); returni+1;}//快速排序voidQuickSort(int*a,intlen)//算法主體函數(shù){ if(len>0) { intq=Partition(a,len); if(q<len-q) { QuickSort(a,q-1); QuickSort(a+q+1,len-q-1); } else { QuickSort(a+q+1,len-q-1); QuickSort(a,q-1); } }}/***********插入式希爾排序****************/希爾排序//希爾插入voidShellInsert(int*a,intinc,intlen){ for(inti=inc;i<len;i+=inc) { intj=i,x=a[i]; while(j>0&&a[j-inc]>x) a[j]=a[j-inc],j-=inc; a[j]=x; }}//插入式希爾排序voidShellSort(int*a,intlen)//算法主體函數(shù){ intinc=len; do { inc=inc/3+1; for(ints=0;s<inc;s++) ShellInsert(a-s,inc,len+s); } while(inc>1);}/********************************/同余運(yùn)算(1〕ifa≡b(Modm)andc≡d(Modm),thena+c≡b+d(Modm)(2〕ifa≡b(Modm)andc≡d(Modm),thenac≡bd(Modm)(3〕ifa≡b(Modm)k>0,thenak≡bk(Modmk)(4〕ifa≡b(Modm)andd|a,d|b,d|m,thena/d≡b/d(Modm/d)(5〕ifa≡b(Modm)andd|m,thena≡b(Modd)(6〕ifca≡cb(Modm)andd=gcd(c,m),thena≡b(Modm/d)假設(shè)a≡0(Modm)，稱a被m整除模線性方程問(wèn)題/*求最小的N，使得A+C*N==B(mod2^k)。也就是求模線性方程C*N==B-A(mod2^k)的最小解,N<4^k推論1：方程ax=b(modn)對(duì)于未知量x有解，當(dāng)且僅當(dāng)gcd(a,n)|b。推論2：方程ax=b(modn)或者對(duì)模n有d個(gè)不同的解，其中d=gcd(a,n)，或者無(wú)解。定理1：設(shè)d=gcd(a,n)，假定對(duì)整數(shù)x和y滿足d=ax+by(比方用擴(kuò)展Euclid算法求出的一組解)。如果d|b，那么方程ax=b(modn)有一個(gè)解x0滿足x0=x*(b/d)modn。特別的設(shè)e=x0+n，方程ax=b(modn)的最小整數(shù)解x1=emod(n/d)，最大整數(shù)解x2=x1+(d-1)*(n/d)。定理2：假設(shè)方程ax=b(modn)有解，且x0是方程的任意一個(gè)解，那么該方程對(duì)模n恰有d個(gè)不同的解(d=gcd(a,n))，分別為：xi=x0+i*(n/d)modn。以上定理的具體證明見(jiàn)《算法導(dǎo)論》*/#include<iostream>#include<cmath>usingnamespacestd;#definemod(a,b)((a)%(b)+(b))%(b)//把負(fù)數(shù)轉(zhuǎn)化成為正數(shù)typedeflonglongint64;int64ext_euclid(int64a,int64b,int64&x,int64&y){ int64t,d; if(b==0) { x=1; y=0; returna; } d=ext_euclid(b,mod(a,b),x,y); t=x; x=y; y=t-a/b*y; returnd;}voidmodular_linear_equation_solver(int64a,int64b,int64n){ int64d; int64x,y; d=ext_euclid(a,n,x,y); if(mod(b,d)>0) cout<<"FOREVER"<<endl; elsecout<<mod((x*(b/d)),n/d)<<endl;}intmain(){ int64a,b,c,n; intk; while(cin>>a>>b>>c>>k) { if(!a&&!b&&!c&&!k) break; n=pow(2.0,k); modular_linear_equation_solver(c,b-a,n); } return0;}方法二：#ifdefWIN32typedef__int64i64;#elsetypedeflonglongi64;#endif//擴(kuò)展Euclid求解gcd(a,b)=ax+byintext_gcd(inta,intb,int&x,int&y){ intt,ret; if(!b){ x=1,y=0; returna; } ret=ext_gcd(b,a%b,x,y); t=x,x=y,y=t-a/b*y; returnret;}//計(jì)算m^a,O(loga),本身沒(méi)什么用,注意這個(gè)按位處理的方法:-Pintexponent(intm,inta){ intret=1; for(;a;a>>=1,m*=m) if(a&1) ret*=m; returnret;}//計(jì)算冪取模a^bmodn,O(logb)intmodular_exponent(inta,intb,intn){//a^bmodn intret=1; for(;b;b>>=1,a=(int)((i64)a)*a%n) if(b&1) ret=(int)((i64)ret)*a%n; returnret;}//求解模線性方程ax=b(modn)//返回解的個(gè)數(shù),解保存在sol[]中//要求n>0,解的范圍0..n-1intmodular_linear(inta,intb,intn,int*sol){ intd,e,x,y,i; d=ext_gcd(a,n,x,y); if(b%d) return0; e=(x*(b/d)%n+n)%n; for(i=0;i<d;i++) sol[i]=(e+i*(n/d))%n; returnd;}//求解模線性方程組(中國(guó)余數(shù)定理)//x=b[0](modw[0])//x=b[1](modw[1])//...//x=b[k-1](modw[k-1])//要求w[i]>0,w[i]與w[j]互質(zhì),解的范圍1..n,n=w[0]*w[1]*...*w[k-1]intmodular_linear_system(intb[],intw[],intk){ intd,x,y,a=0,m,n=1,i; for(i=0;i<k;i++) n*=w[i]; for(i=0;i<k;i++){ m=n/w[i]; d=ext_gcd(w[i],m,x,y); a=(a+y*m*b[i])%n; } return(a+n)%n;}計(jì)算a^nmodk//k<40000intpowmod(inta,intn,intk){intd=1;for(a%=k;n>0;n>>=1){if(n&1)d=(d*a)%k;a=(a*a)%k;}returnd;}階乘最后非0位//求階乘最后非零位,復(fù)雜度O(nlogn)//返回該位,n以字符串方式傳入#include<string.h>#defineMAXN10000intlastdigit(char*buf){ constintmod[20]={1,1,2,6,4,2,2,4,2,8,4,4,8,4,6,8,8,6,8,2}; intlen=strlen(buf),a[MAXN],i,c,ret=1; if(len==1) returnmod[buf[0]-'0']; for(i=0;i<len;i++) a[i]=buf[len-1-i]-'0'; for(;len;len-=!a[len-1]){ ret=ret*mod[a[1]%2*10+a[0]]%5; for(c=0,i=len-1;i>=0;i--) c=c*10+a[i],a[i]=c/5,c%=5; } returnret+ret%2*5;}素?cái)?shù)篇除了1和此整數(shù)自身外，沒(méi)法被其他自然數(shù)整除的數(shù)，又稱質(zhì)數(shù)。方法一：voidprim(){ longi,j,k; prime[0]=2; prime[1]=3; jue[2]=true; jue[3]=true; jue[5]=true; for(i=5,k=2;i<999983;i+=2) { for(j=0;prime[j]*prime[j]<=i&&i%prime[j];) { j++; if(prime[j]*prime[j]>i) { prime[k++]=i; jue[i]=true; } } }}方法二：#include<string.h>boolused[21000];voidgetprimes(){ memset(used,true,sizeof(used)); used[0]=false; used[1]=false; for(inti=2;i<=21000;i++) { if(used[i]) for(intj=2*i;j<=21000;j+=i) used[j]=false; }}線性篩法constintUPBOUND=100000;inta[UPBOUND];intp[UPBOUND],pn;//號(hào)稱線性的篩素?cái)?shù)算法，實(shí)際性能確實(shí)不錯(cuò)//p[]={2,3,5,7,...},pn為小于UPBOUND的素?cái)?shù)個(gè)數(shù)//假設(shè)i是合數(shù)a[i]為i的最小因子，假設(shè)i是素?cái)?shù)a[i]=0voidprimefilter(){inti,j;for(i=2;i<UPBOUND;++i) { if(!(a[i]))p[pn++]=i; for(j=0;(j<pn&&i*p[j]<UPBOUND&&(p[j]<=a[i]||a[i]==0));++j) a[i*p[j]]=p[j]; }}voidprim()//建立素?cái)?shù)表{ longlongi,j,k; prime[0]=2; prime[1]=3; for(i=5,k=2;i<47000;i+=2) { for(j=1;prime[j]*prime[j]<=i&&i%prime[j];j++); if(prime[j]*prime[j]>i) prime[k++]=i; }}voidgetprimes()//構(gòu)建素?cái)?shù)表{ inti; primes[1]=1;for(i=2;i<=32;i++) { if(!primes[i]) for(intj=2*i;j<=32;j+=i) primes[j]=1; }}費(fèi)馬小定理假設(shè)p為素?cái)?shù)，a為正整數(shù)，那么一定有a^p≡a(Modp)MR素性測(cè)試給定整數(shù)a，假設(shè)滿足a^p≡a(Modp)，p為一個(gè)素?cái)?shù)，那么a很可能也是素?cái)?shù)歐拉函數(shù)問(wèn)題#include<stdio.h>intmain(){longn,i,k;doubler;while(scanf("%ld",&n)&&n) { r=n; i=2;while(n>1) { k=0;while(n%i==0) {n/=i; k=1; }if(k) r*=1.0-1.0/i;if(i==2)i++;else i=i+2; }printf("%.0lf\n",r); }return0;}巴赫猜測(cè)/*哥德巴赫猜測(cè):每一個(gè)數(shù)最多可由3個(gè)素?cái)?shù)相加表示，任意一個(gè)大于4的偶數(shù)必定可以表示為兩奇素?cái)?shù)之和*/#include<stdio.h>intcnt,n,tmp;intff[10001],f[10001],b[10001],primes[3000];voidprime(){inti,j,t;for(i=0;i<10001;i++)ff[i]=0;for(i=2;i<=100;i++) {if(ff[i])continue; j=i*i;while(j<=10000){ff[j]=1; j+=i; } }cnt=0;for(i=2;i<=10000;i++)if(ff[i]==0)primes[cnt++]=i;for(i=0;i<10001;i++)f[i]=-1;f[0]=0;for(i=0;i<cnt;i++) { t=primes[i];for(j=t;j<=3*t;j++) { /////***************和包含t的數(shù)中，最小為t，最大為t+t+tif(j>10000)break;if(f[j-t]!=-1&&(f[j]==-1||f[j]>f[j-t]+1)) {f[j]=f[j-t]+1;b[j]=t; } } }}intmain(){prime();while(scanf("%d",&n)!=EOF) {if(n<=1)printf("0\n");else {if(ff[n]==0) {printf("1\n");printf("%d\n",n);continue; }else {printf("%d\n",f[n]);while(n>0) {printf("%d",b[n]);n-=b[n];if(n==0)printf("\n");elseprintf(""); } } } }return0;}最大公約數(shù)intgcd(inta,intb)//遞歸實(shí)現(xiàn){return(b?gcd(b,a%b):a);}intgcd(inta,intb)//非遞歸實(shí)現(xiàn){while(b){intt=a%b;a=b;b=t;}returna;}最小公倍數(shù)lcm(a,b)=a/gcd(a,b)*b不定方程求解二元線性不定方程：形如ax+by=c不定方程求解程序：對(duì)于方程ax+by=gcd(a,b)voideuclid_gcd(inta,intb,int&d,int&x,int&y){if(!b){d=a;x=1;y=0;}else{ euclid_gcd(b,a%b,d,y,x); y-=x*(a/b); }}概率因子分解Pollard算法typedef__int64Long;//或自定義大整數(shù)類〔必須重載運(yùn)算符〕LongPollard(Longn){ Longi=1,x=rand()%n,y=x,k=2;while(1) { ++i; x=(x*x-1)%n; Longd=gcd(y-x,n);if(d>1&&d<n)returnd;if(i==k) { y=x;k*=2; } }return-1;}數(shù)值計(jì)算[2]定積分計(jì)算(Romberg)/*Romberg求定積分輸入：積分區(qū)間[a,b]，被積函數(shù)f(x,y,z)輸出：積分結(jié)果f(x,y,z)例如：doublef0(doublex,doublel,doublet){returnsqrt(1.0+l*l*t*t*cos(t*x)*cos(t*x));}*/doubleIntegral(doublea,doubleb,double(*f)(doublex,doubley,doublez),doubleeps,doublel,doublet)doubleRomberg(doublea,doubleb,double(*f)(doublex,doubley,doublez),doubleeps,doublel,doublet){#defineMAX_N1000inti,j,temp2,min;doubleh,R[2][MAX_N],temp4;for(i=0;i<MAX_N;i++){R[0][i]=0.0;R[1][i]=0.0; } h=b-a;min=(int)(log(h*10.0)/log(2.0));//hshouldbeatmost0.1R[0][0]=((*f)(a,l,t)+(*f)(b,l,t))*h*0.50; i=1; temp2=1;while(i<MAX_N){i++;R[1][0]=0.0;for(j=1;j<=temp2;j++)R[1][0]+=(*f)(a+h*((double)j-0.50),l,t);R[1][0]=(R[0][0]+h*R[1][0])*0.50; temp4=4.0;for(j=1;j<i;j++){R[1][j]=R[1][j-1]+(R[1][j-1]-R[0][j-1])/(temp4-1.0); temp4*=4.0; }if((fabs(R[1][i-1]-R[0][i-2])<eps)&&(i>min))returnR[1][i-1];h*=0.50; temp2*=2;for(j=0;j<i;j++)R[0][j]=R[1][j]; }returnR[1][MAX_N-1];}doubleIntegral(doublea,doubleb,double(*f)(doublex,doubley,doublez),doubleeps,doublel,doublet){intn;doubleR,p,res; n=(int)(floor)(b*t*0.50/pi); p=2.0*pi/t;res=b-(double)n*p;if(n) R=Romberg(a,p,f0,eps/(double)n,l,t); R=R*(double)n+Romberg(0.0,res,f0,eps,l,t);returnR/100.0;}多項(xiàng)式求根(牛頓法)/*牛頓法解多項(xiàng)式的根輸入：多項(xiàng)式系數(shù)c[]，多項(xiàng)式度數(shù)n，求在[a,b]間的根輸出：根要求保證[a,b]間有根*/doublefabs(doublex){return(x<0)?-x:x;}doublef(intm,doublec[],doublex){inti;doublep=c[m];for(i=m;i>0;i--) p=p*x+c[i-1];returnp;}intnewton(doublex0,double*r,doublec[],doublecp[],intn,doublea,doubleb,doubleeps){intMAX_ITERATION=1000;inti=1;doublex1,x2,fp,eps2=eps/10.0;x1=x0;while(i<MAX_ITERATION){x2=f(n,c,x1);fp=f(n-1,cp,x1);if((fabs(fp)<0.000000001)&&(fabs(x2)>1.0))return0;x2=x1-x2/fp;if(fabs(x1-x2)<eps2){if(x2<a||x2>b)return0; *r=x2;return1; }x1=x2;i++; }return0;}doublePolynomial_Root(doublec[],intn,doublea,doubleb,doubleeps){double*cp;inti;doubleroot;cp=(double*)calloc(n,sizeof(double));for(i=n-1;i>=0;i--){cp[i]=(i+1)*c[i+1]; }if(a>b){root=a;a=b;b=root; }if((!newton(a,&root,c,cp,n,a,b,eps))&&(!newton(b,&root,c,cp,n,a,b,eps)))newton((a+b)*0.5,&root,c,cp,n,a,b,eps);free(cp);if(fabs(root)<eps)returnfabs(root);elsereturnroot;}周期性方程(追趕法)/*追趕法解周期性方程周期性方程定義：|a1b1c1...|=x1|a2b2c2...|=x2|...|*X=...|cn-1...an-1bn-1|=xn-1|bncnan|=xn輸入：a[],b[],c[],x[]輸出：求解結(jié)果X在x[]中*/voidrun(){ c[0]/=b[0];a[0]/=b[0];x[0]/=b[0]; for(inti=1;i<N-1;i++){ doubletemp=b[i]-a[i]*c[i-1]; c[i]/=temp; x[i]=(x[i]-a[i]*x[i-1])/temp; a[i]=-a[i]*a[i-1]/temp; } a[N-2]=-a[N-2]-c[N-2]; for(inti=N-3;i>=0;i--){ a[i]=-a[i]-c[i]*a[i+1]; x[i]-=c[i]*x[i+1]; } x[N-1]-=(c[N-1]*x[0]+a[N-1]*x[N-2]); x[N-1]/=(c[N-1]*a[0]+a[N-1]*a[N-2]+b[N-1]); for(inti=N-2;i>=0;i--) x[i]+=a[i]*x[N-1];}組合論[3]組合公式1.C(m,n)=C(m,m-n)2.C(m,n)=C(m-1,n)+C(m-1,n-1)derangementD(n)=n!(1-1/1!+1/2!-1/3!+...+(-1)^n/n!)=(n-1)(D(n-2)-D(n-1))Q(n)=D(n)+D(n-1)求和公式,k=1..n1.sum(k)=n(n+1)/22.sum(2k-1)=n^23.sum(k^2)=n(n+1)(2n+1)/64.sum((2k-1)^2)=n(4n^2-1)/35.sum(k^3)=(n(n+1)/2)^26.sum((2k-1)^3)=n^2(2n^2-1)7.sum(k^4)=n(n+1)(2n+1)(3n^2+3n-1)/308.sum(k^5)=n^2(n+1)^2(2n^2+2n-1)/129.sum(k(k+1))=n(n+1)(n+2)/310.sum(k(k+1)(k+2))=n(n+1)(n+2)(n+3)/412.sum(k(k+1)(k+2)(k+3))=n(n+1)(n+2)(n+3)(n+4)/5全組合排列方法一：#defineMAX_N10intn;//共n個(gè)數(shù)intrcd[MAX_N];//記錄每個(gè)位置填的數(shù)intused[MAX_N];//標(biāo)記數(shù)是否用過(guò)intnum[MAX_N];//存放輸入的n個(gè)數(shù)voidfull_permutation(intL){ inti; if(L==n+1) { //輸出 return; } for(i=1;i<=n;i++)//枚舉所有的數(shù)，循環(huán)從0開始 if(!used[i]){//num[i]沒(méi)有使用過(guò) used[i]=1;//標(biāo)記為已使用 rcd[L]=i;//在l位置放上該數(shù) full_permutation(L+1);//填下一個(gè)位置 used[i]=0;//清標(biāo)記 }}方法二：#include<iostream>usingnamespacestd;intx[11]={0,1,2,3,4,5,6,7,8,9,10};voidpermute(intt)//全排列{ if(t>n) output(); else { for(inti=t;i<=n;i++) { swap(x[t],x[i]); permute(t+1); swap(x[t],x[i]); } }}測(cè)試函數(shù)SampleInput3123SampleOutput123132213231312321//Program#include<stdio.h>#include<string.h>constintmaxn=11;intn;intused[maxn];//標(biāo)記數(shù)組intmat[maxn];//存儲(chǔ)數(shù)組intnum[maxn];//輸出數(shù)組voidsolve(intl){ if(l>=n) { for(inti=0;i<n;++i)printf("%d",num[i]); puts(""); return; } for(inti=0;i<n;++i) { if(!used[i]) { used[i]=1; num[l]=mat[i]; solve(l+1); used[i]=0; } }}intmain(){ while(scanf("%d",&n)!=EOF) { for(inti=0;i<n;++i)scanf("%d",mat+i); memset(used,0,sizeof(used)); solve(0); } return0;}非重復(fù)組合排列含重復(fù)數(shù)字時(shí)，生成不重復(fù)組合排列SampleInput41223SampleOutput122312321322212321322213223123122321312232123221//Program#include<stdio.h>constintmaxn=10;intn,var;intIndex;intused[maxn],mat[maxn],num[maxn];voidpush(intvarNum){ //壓棧for(inti=0;i<Index;++i){if(mat[i]==varNum){++used[i];return;}}mat[Index]=varNum;++used[Index++];}voidsolve(intl){ //求解if(l>=n){for(inti=0;i<n;++i)printf("%d",num[i]);puts("");return;}for(inti=0;i<Index;++i){if(used[i]){used[i]--;num[l]=mat[i];solve(l+1);used[i]++;}}}intmain(){while(scanf("%d",&n)!=EOF){Index=0;for(inti=0;i<n;++i){scanf("%d",&var);push(var);}solve(0);}return0;}類循環(huán)組合排列SampleInput：42SampleOutput0000000100100011010001010110011110001001101010111100110111101111//Program#include<stdio.h>intn,m;intmat[10];voidsolve(intl){ if(l>=n) { for(inti=0;i<n;++i) printf("%d",mat[i]); puts(""); return; } for(inti=0;i<m;++i) { mat[l]=i; solve(l+1); }}intmain(){ while(scanf("%d%d",&n,&m)!=EOF) { solve(0); } return0;}普通選擇性組合排列SampleInput5312345SampleOutput123124125134135145234235245345//Program#include<stdio.h>constintmaxn=10;inttotalN,selectM;intmat[maxn];//存儲(chǔ)數(shù)組intnum[maxn];//輸出數(shù)組voidsolve(intstartVar,intselectVar){if(selectVar>=selectM){for(inti=0;i<selectM;++i)printf("%d",num[i]);puts("");return;}for(inti=startVar;i<totalN;++i){num[selectVar]=mat[i];solve(i+1,selectVar+1);}}intmain(){while(scanf("%d%d",&totalN,&selectM)!=EOF){for(inti=0;i<totalN;++i)scanf("%d",mat+i);solve(0,0);}return0;}生成全子集組合排列SampleInput41234SampleOutput11212312341241313414223234243344//Program#include<stdio.h>constintmaxn=10;intn;intmat[maxn];intnum[maxn];voidsolve(intcur_totalVar,intnextVar){for(inti=0;i<cur_totalVar;++i)printf("%d",num[i]);if(cur_totalVar)puts("");for(inti=nextVar;i<n;++i){num[cur_totalVar]=mat[i];solve(cur_totalVar+1,i+1);}}intmain(){while(scanf("%d",&n)!=EOF){for(inti=0;i<n;++i)scanf("%d",mat+i);solve(0,0);}return0;}//注意：倘假設(shè)需要輸出空集〔也即輸出一個(gè)換行〕，可做如下修改//在函數(shù)solve()中，將if(cur_totalVar)puts("");改為puts("");非重復(fù)生成全子集組合排列含重復(fù)數(shù)字時(shí)，生成不重復(fù)全子集組合排列SampleInput41223SampleOutput112122122312313222223233//Program#include<stdio.h>constintmaxn=10;intn,var;intIndex;intused[maxn],mat[maxn],num[maxn];voidpush(intvarNum){ //壓棧for(inti=0;i<Index;++i){if(mat[i]==varNum){++used[i];return;}}mat[Index]=varNum;++used[Index++];}voidsolve(intl,intp){ //求解for(inti=0;i<l;++i)printf("%d",num[i]);if(l)puts("");for(inti=p;i<Index;++i){if(used[i]){used[i]--;num[l]=mat[i];solve(l+1,i);used[i]++;}}}intmain(){while(scanf("%d",&n)!=EOF){Index=0;for(inti=0;i<n;++i){scanf("%d",&var);push(var);}solve(0,0);}return0;}//注意：倘假設(shè)需要輸出空集〔也即輸出一個(gè)換行〕，可做如下修改//在函數(shù)solve()中，將if(l)puts("");改為puts("");一般組合select_combination(intStep,intPos){ //已經(jīng)確定Step-1個(gè)數(shù)字,第Step步的數(shù)為X[Pos,…,n]的任一個(gè) if(Step==m+1) {//已確定數(shù)字?jǐn)?shù)目為m時(shí)， Output(); //輸出一種組合 return; }for(i=Pos;i<=n;i++) { A[Step]=X[i]; select_combination(Step+1,Pos+1); }}一般組合的優(yōu)化select_combination(intStep,intPos){ //已經(jīng)確定Step-1個(gè)數(shù)字,第Step步的數(shù)為X[Pos,…,n]的任一個(gè) if(Step==m+1) {//已確定數(shù)字?jǐn)?shù)目為m時(shí)， Output(); //輸出一種組合 return; }for(i=Pos;i<=n-m+Step;i++) { A[Step]=X[i]; select_combination(Step+1,Pos+1); }}總結(jié)：遞歸思想在搜索技術(shù)中有著廣泛的應(yīng)用，應(yīng)當(dāng)熟練掌握和學(xué)習(xí)這種思想，對(duì)求解這一類搜索題目大有裨益。排列組合生成//gen_perm產(chǎn)生字典序排列P(n,m)//gen_comb產(chǎn)生字典序組合C(n,m)//gen_perm_swap產(chǎn)生相鄰位對(duì)換全排列P(n,n)//產(chǎn)生元素用1..n表示//dummy為產(chǎn)生后調(diào)用的函數(shù),傳入a[]和n,a[0]..a[n-1]為一次產(chǎn)生的結(jié)果#defineMAXN100intcount;#include<iostream.h>voiddummy(int*a,intn){ inti; cout<<count++<<":"; for(i=0;i<n-1;i++) cout<<a[i]<<''; cout<<a[n-1]<<endl;}void_gen_perm(int*a,intn,intm,intl,int*temp,int*tag){ inti; if(l==m) dummy(temp,m); else for(i=0;i<n;i++) if(!tag[i]){ temp[l]=a[i],tag[i]=1; _gen_perm(a,n,m,l+1,temp,tag); tag[i]=0; }}voidgen_perm(intn,intm){ inta[MAXN],temp[MAXN],tag[MAXN]={0},i; for(i=0;i<n;i++) a[i]=i+1; _gen_perm(a,n,m,0,temp,tag);}void_gen_comb(int*a,ints,inte,intm,int&count,int*temp){ inti; if(!m) dummy(temp,count); else for(i=s;i<=e-m+1;i++){ temp[count++]=a[i]; _gen_comb(a,i+1,e,m-1,count,temp); count--; }}voidgen_comb(intn,intm){ inta[MAXN],temp[MAXN],count=0,i; for(i=0;i<n;i++) a[i]=i+1; _gen_comb(a,0,n-1,m,count,temp);}void_gen_perm_swap(int*a,intn,intl,int*pos,int*dir){ inti,p1,p2,t; if(l==n) dummy(a,n); else{ _gen_perm_swap(a,n,l+1,pos,dir); for(i=0;i<l;i++){ p2=(p1=pos[l])+dir[l]; t=a[p1],a[p1]=a[p2],a[p2]=t; pos[a[p1]-1]=p1,pos[a[p2]-1]=p2; _gen_perm_swap(a,n,l+1,pos,dir); } dir[l]=-dir[l]; }}voidgen_perm_swap(intn){ inta[MAXN],pos[MAXN],dir[MAXN],i; for(i=0;i<n;i++) a[i]=i+1,pos[i]=i,dir[i]=-1; _gen_perm_swap(a,n,0,pos,dir);}生成gray碼//生成reflectedgraycode//每次調(diào)用gray取得下一個(gè)碼//000...000是第一個(gè)碼,100...000是最后一個(gè)碼voidgray(intn,int*code){ intt=0,i; for(i=0;i<n;t+=code[i++]); if(t&1) for(n--;!code[n];n--); code[n-1]=1-code[n-1];}置換(polya)//求置換的循環(huán)節(jié),polya原理//perm[0..n-1]為0..n-1的一個(gè)置換(排列)//返回置換最小周期,num返回循環(huán)節(jié)個(gè)數(shù)#defineMAXN1000intgcd(inta,intb){ returnb?gcd(b,a%b):a;}intpolya(int*perm,intn,int&num){ inti,j,p,v[MAXN]={0},ret=1; for(num=i=0;