组合数学一些结论

第一章有关数论的算法1.1最大公约数与最小公倍数function gcd(a,b:longint):longint;beginif a mod b=0 then gcd:=b else gcd:=gcd(b,a mod b);end;1.算法1: 欧几里德算法求a，b的最大公约数function gcd(a,b:longint):longint;beginif b=0 then gcdd:=aelse gcd:=gcd(b,a mod b);end;2.算法2:最小公倍数acm=a*b div gcd(a,b);function gcd(a,b:longint):longint;beginif a mod b=0 then gcd:=b else gcd:=gcd(b,a mod b);end;3.算法3:扩展的欧几里德算法，求出gcd(a,b)和满足gcd(a,b)=ax+by的整数x和y （一组解）function exgcd(a,b:longint;var x,y:longint):longint;var t:longint;beginif b=0 then begin exgcd:=a; x:=1; y:=0; endelsebeginexgcdt:=exgcd(b,a mod b,x,y);t:=x; x:=y; y:=t-(a div b)*y;end;end;（理论依据：gcd(a,b)=ax+by=bx1+(a mod b)y1=bx1+(a-(a div b)*b)y1=ay1+b(x1-(a div b)*y1)）1. 2有关素数的算法1.算法4:求前n个素数:program BasicMath_Prime;const maxn=1000;var pnum,n:longint;p:array[1..maxn] of longint;function IsPrime(x:longint):boolean;var i:integer;beginfor i:=1 to pnum doif sqr(p[i])<=x thenbeginif x mod p[i]=0 then begin IsPrime:=false; exit; end;endelse begin IsPrime:=true; exit; end;IsPrime:=true;end;procedure main;var x:longint;beginpnum:=0; x:=1;while(pnum<n) dobegininc(x);if IsPrime(x) then begin inc(pnum); p[pnum]:=x; end;end;end;procedure out;var i,t:integer;beginfor i:=1 to n dobeginwrite(p[i]:5);t:=t+1;if t mod 10=0 then writeln;end;end;begin readln(n); main; out; end.2.算法5:求不大于n的所有素数program sushu3;const maxn=10000;var i,k,n:integer;a:array[1..maxn] of integer; beginreadln(n);for i:=1 to n do a[i]:=i;a[1]:=0; i:=2;while i<n dobegink:=2*i;while k<=n dobegina[k]:=0;k:=k+i;end;i:=i+1;while (a[i]=0) and (i<n) do i:=i+1; end;k:=0;for i:=1 to n doif a[i]<>0 thenbeginwrite(a[i]:5); k:=k+1;if k mod 10 =0 then writeln;endend.3.算法6:将整数分解质因数的积program BasicMath_PolynomialFactors; constmaxp=1000;varpnum,n:longint;num,p:array[1..maxp] of longint; procedure main;var x:longint;beginfillchar(num,sizeof(num),0);fillchar(p,sizeof(p),0);pnum:=0;x:=1;while(n>1) dobegininc(x);if n mod x=0 thenbegininc(pnum);p[pnum]:=x;while(n mod x=0) dobeginn:=n div x;inc(num[pnum]);end;end;end;end;procedure out;var j,i:integer;beginfor i:=1 to pnum dofor j:=1 to num[i] dowrite(p[i]:5);writeln;end;beginmain;out;end.1.3方程ax+by=c的整数解及应用1.算法7：求方程ax+by=c的整数解procedure equation(a,b,c:longint;var x0,y0:longint); var d,x,y:longint;begind:=exgcd(a,b,x,y);if c mod d>0 thenbeginwriteln('no answer');halt;end elsebeginx0:=x*(c div d);y0:=y*(c div d);end;end;2.方程ax+by=c整数解的应用例1：有三个分别装有a升水、b升水和c升水的量筒(gcd(a，b)＝1，c>b>a>0),现c筒装满水，问能否在c筒个量出d升水(c>d>0)。

若能，请列出一种方案。

算法分析：量水过程实际上就是倒来倒去，每次倒的时候总有如下几个持点：1.总有一个筒中的水没有变动；2．不是一个筒被倒满就是另一个筒被倒光；3．c筒仅起中转作用，而本身容积除了必须足够装下a简和b简的全部水外，别无其它限制。

程序如下:program mw;typenode=array[0..1] of longint;vara,b,c:node;d,step,x,y:longint;function exgcd(a,b:longint;var x,y:longint):longint;var t:longint;beginif b=0 thenbeginexgcd:=a;;x:=1;y:=0;endelsebeginexgcd:=exgcd(b,a mod b,x,y);t:=x;x:=y;y:=t-(a div b)*yend;end;procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;begind:=exgcd(a,b,x,y);if c mod d>0 thenbeginwriteln('no answer');halt;end elsebeginx0:=x*(c div d);y0:=y*(c div d);end;end;procedure fill(var a,b:node);var t:longint;beginif a[1]<b[0]-b[1] then t:=a[1]else t:=b[0]-b[1];a[1]:=a[1]-t;b[1]:=b[1]+tend;beginwrite('a,b,c,d=');readln(a[0],b[0],c[0],d);equation(a[0],b[0],d,x,y);step:=0;a[1]:=0;b[1]:=0;c[1]:=c[0];writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);if x>0 thenrepeatif a[1]=0 then fill(c,a) elseif b[1]=b[0] then fill(b,c) else fill(a,b); inc(step);writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);until c[1]=delserepeatif b[1]=0 then fill(c,b) elseif a[1]=a[0] then fill(a,c) else fill(b,a); inc(step);writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);until c[1]=d;end.1.4求a^b mod n1.算法8:直接叠代法求a^b mod nfunction f(a,b,n:longint): longint; var d,i:longint;begind:=a;for i:=2 to b do d:=d mod n*a;d:=d mod n;f:=d;end;2.算法9:加速叠代法function f(a,b,n:longint):longint; var d,t:longint;begind:=1;t:=a;while b>0 dobeginif t=1 then beginf:=d;exit end ;if b mod 2 =1 then d:=d*t mod n;b:=b div 2;t:=t*t mod n;f:=dend;第二章高精度计算2.1高精度加法高精度加法程序如下：program HighPrecision1_Plus;constfn_inp='hp1.inp';fn_out='hp1.out';maxlen=100; { max length of the number } typehp=recordlen:integer; { length of the number }s:array[1..maxlen] of integer{ s[1] is the lowest positions[len] is the highest position }end;varx:array[1..2] of hp;y:hp; { x:input ; y:output }procedure PrintHP(const p:hp);var i:integer;beginfor i:=p.len downto 1 do write(p.s[i]);end;procedure init;varst:string;j,i:integer;beginassign(input,fn_inp);reset(input);for j:=1 to 2 dobeginreadln(st);x[j].len:=length(st);for i:=1 to x[j].len do { change string to HP }x[j].s[i]:=ord(st[x[j].len+1-i])-ord('0');close(input);end;procedure Plus(a,b:hp;var c:hp); { c:=a+b }var i,len:integer;beginfillchar(c,sizeof(c),0);if a.len>b.len then len:=a.len { get the bigger length of a,b } else len:=b.len;for i:=1 to len do { plus from low to high }begininc(c.s[i],a.s[i]+b.s[i]);if c.s[i]>=10 thenbegindec(c.s[i],10);inc(c.s[i+1]); { add 1 to a higher position }end;end;if c.s[len+1]>0 then inc(len);c.len:=len;end;procedure main;beginPlus(x[1],x[2],y);end;procedure out;beginassign(output,fn_out);rewrite(output);PrintHP(y);writeln;close(output);end;begin init; main; out; end.2. 2 高精度减法高精度减法程序如下：program HighPrecision2_Subtract;constfn_inp='hp2.inp';fn_out='hp2.out';maxlen=100; { max length of the number }typehp=recordlen:integer; { length of the number }s:array[1..maxlen] of integer { s[1] is the lowest positions[len] is the highest position }end;varx:array[1..2] of hp;y:hp; { x:input ; y:output }positive:boolean;procedure PrintHP(const p:hp);var i:integer;beginfor i:=p.len downto 1 do write(p.s[i]);end;procedure init;varst:string; j,i:integer;beginassign(input,fn_inp);reset(input);for j:=1 to 2 dobeginreadln(st);x[j].len:=length(st);for i:=1 to x[j].len do { change string to HP }x[j].s[i]:=ord(st[x[j].len+1-i])-ord('0');end;close(input);end;procedure Subtract(a,b:hp;var c:hp); { c:=a-b, suppose a>=b }var i,len:integer;beginfillchar(c,sizeof(c),0);if a.len>b.len then len:=a.len { get the bigger length of a,b } else len:=b.len;for i:=1 to len do { subtract from low to high }begininc(c.s[i],a.s[i]-b.s[i]);if c.s[i]<0 thenbegininc(c.s[i],10);dec(c.s[i+1]); { add 1 to a higher position }end;end;while(len>1) and (c.s[len]=0) do dec(len);c.len:=len;end;function Compare(const a,b:hp):integer;{1 if a>b0 if a=b-1 if a<b}var len:integer;beginif a.len>b.len then len:=a.len { get the bigger length of a,b } else len:=b.len;while(len>0) and (a.s[len]=b.s[len]) do dec(len);{ find a position which have a different digit }if len=0 then compare:=0 { no difference }else compare:=a.s[len]-b.s[len];end;procedure main;beginif Compare(x[1],x[2])<0 then positive:=falseelse positive:=true;if positive then Subtract(x[1],x[2],y)else Subtract(x[2],x[1],y);end;procedure out;beginassign(output,fn_out);rewrite(output);if not positive then write('-');PrintHP(y);writeln;close(output);end;begin init; main; out; end.2.３高精度乘法1.高精度乘单精度(1位数)程序如下:program HighPrecision3_Multiply1;constfn_inp='hp3.inp';fn_out='hp3.out';maxlen=100; { max length of the number }typelen:integer; { length of the number }s:array[1..maxlen] of integer{ s[1] is the lowest positions[len] is the highest position }end;varx,y:hp; { x:input hp ; y:output }z:integer; { z:input lp }procedure PrintHP(const p:hp);var i:integer;beginfor i:=p.len downto 1 do write(p.s[i]);end;procedure init;varst:string;i:integer;beginassign(input,fn_inp);reset(input);readln(st);x.len:=length(st);for i:=1 to x.len do { change string to HP }x.s[i]:=ord(st[x.len+1-i])-ord('0');readln(z);close(input);end;procedure Multiply(a:hp;b:integer;var c:hp); { c:=a*b } var i,len:integer;beginfillchar(c,sizeof(c),0);len:=a.len;for i:=1 to len dobegininc(c.s[i],a.s[i]*b);inc(c.s[i+1],c.s[i] div 10);c.s[i]:=c.s[i] mod 10;end;inc(len);while(c.s[len]>=10) dobegininc(c.s[len+1],c.s[len] div 10);c.s[len]=c.s[len] mod 10;end;while(len>1) and (c.s[len]=0) do dec(len);c.len:=len;end;procedure main;beginMultiply(x,z,y);end;procedure out;beginassign(output,fn_out);rewrite(output);PrintHP(y);writeln;close(output);end;begininit;main;out;end.2.高精度乘一个整型数据(integer)只需要将上述程序的hp类型定义如下即可: typehp=recordlen:integer { length of the number }s:array[1..maxlen] of longint{ s[1] is the lowest positions[len] is the highest position }end;3.高精度乘高精度程序如下:program HighPrecision4_Multiply2;constfn_inp='hp4.inp';fn_out='hp4.out';maxlen=100; { max length of the number } typehp=recordlen:integer; { length of the number }s:array[1..maxlen] of integer{ s[1] is the lowest positions[len] is the highest position }end;varx:array[1..2] of hp;y:hp; { x:input ; y:output }procedure PrintHP(const p:hp);var i:integer;beginfor i:=p.len downto 1 do write(p.s[i]);end;procedure init;varst:string;j,i:integer;beginassign(input,fn_inp);reset(input);for j:=1 to 2 dobeginreadln(st);x[j].len:=length(st);for i:=1 to x[j].len do { change string to HP }x[j].s[i]:=ord(st[x[j].len+1-i])-ord('0');end;close(input);end;procedure Multiply(a,b:hp;var c:hp); { c:=a+b }var i,j,len:integer;beginfillchar(c,sizeof(c),0);for i:=1 to a.len dofor j:=1 to b.len dobegininc(c.s[i+j-1],a.s[i]*b.s[j]);inc(c.s[i+j],c.s[i+j-1] div 10);c.s[i+j-1]:=c.s[i+j-1] mod 10;end;len:=a.len+b.len+1;{the product of a number with i digits and a number with j digits can only have at most i+j+1 digits}while(len>1)and(c.s[len]=0) do dec(len);c.len:=len;end;procedure main;beginMultiply(x[1],x[2],y);end;procedure out;beginassign(output,fn_out);rewrite(output);PrintHP(y);writeln;close(output);end;begininit;main;out;end.2.4 高精度除法1.高精度除以整型数据(integer);程序如下:program HighPrecision3_Multiply1;constfn_inp='hp5.inp';fn_out='hp5.out';maxlen=100; { max length of the number } typehp=recordlen:integer; { length of the number }s:array[1..maxlen] of integer{ s[1] is the lowest positions[len] is the highest position }end;varx,y:hp;z,w:integer;procedure PrintHP(const p:hp);var i:integer;beginfor i:=p.len downto 1 do write(p.s[i]); end;procedure init;varst:string;i:integer;beginassign(input,fn_inp);reset(input);readln(st);x.len:=length(st);for i:=1 to x.len do { change string to HP }x.s[i]:=ord(st[x.len+1-i])-ord('0');readln(z);close(input);end;procedure Divide(a:hp;b:integer;var c:hp;var d:integer); { c:=a div b ; d:=a mod b }var i,len:integer;beginfillchar(c,sizeof(c),0);len:=a.len;d:=0;for i:=len downto 1 do { from high to low }begind:=d*10+a.s[i];c.s[i]:=d div b;d:=d mod b;end;while(len>1) and (c.s[len]=0) do dec(len);c.len:=len;end;procedure main;beginDivide(x,z,y,w);end;procedure out;beginassign(output,fn_out);rewrite(output);PrintHP(y);writeln;writeln(w);close(output);end;begininit;main;out;end.2.高精度除以高精度程序如下:program HighPrecision4_Multiply2;constfn_inp='hp6.inp';fn_out='hp6.out';maxlen=100; { max length of the number }typehp=recordlen:integer; { length of the number }s:array[1..maxlen] of integer{ s[1] is the lowest positions[len] is the highest position }end;varx:array[1..2] of hp;y,w:hp; { x:input ; y:output }procedure PrintHP(const p:hp);var i:integer;beginfor i:=p.len downto 1 do write(p.s[i]);end;procedure init;varst:string;j,i:integer;beginassign(input,fn_inp);reset(input);for j:=1 to 2 dobeginreadln(st);x[j].len:=length(st);for i:=1 to x[j].len do { change string to HP }x[j].s[i]:=ord(st[x[j].len+1-i])-ord('0');end;close(input);end;procedure Subtract(a,b:hp;var c:hp); { c:=a-b, suppose a>=b } var i,len:integer;beginfillchar(c,sizeof(c),0);if a.len>b.len then len:=a.len { get the bigger length of a,b } else len:=b.len;for i:=1 to len do { subtract from low to high }begininc(c.s[i],a.s[i]-b.s[i]);if c.s[i]<0 thenbegininc(c.s[i],10);dec(c.s[i+1]); { add 1 to a higher position }end;end;while(len>1) and (c.s[len]=0) do dec(len);c.len:=len;end;function Compare(const a,b:hp):integer;{1 if a>b0 if a=b-1 if a<b}var len:integer;beginif a.len>b.len then len:=a.len { get the bigger length of a,b } else len:=b.len;while(len>0) and (a.s[len]=b.s[len]) do dec(len);{ find a position which have a different digit }if len=0 then compare:=0 { no difference }else compare:=a.s[len]-b.s[len];end;procedure Multiply10(var a:hp); { a:=a*10 }var i:Integer;beginfor i:=a.len downto 1 doa.s[i+1]:=a.s[i];a.s[1]:=0;inc(a.len);while(a.len>1) and (a.s[a.len]=0) do dec(a.len);end;procedure Divide(a,b:hp;var c,d:hp); { c:=a div b ; d:=a mod b } var i,j,len:integer;beginfillchar(c,sizeof(c),0);len:=a.len;fillchar(d,sizeof(d),0);for i:=len downto 1 dobeginMultiply10(d);d.s[1]:=a.s[i]; { d:=d*10+a.s[i] }{ c.s[i]:=d div b ; d:=d mod b; }{ while(d>=b) do begin d:=d-b;inc(c.s[i]) end }while(compare(d,b)>=0) dobeginSubtract(d,b,d);inc(c.s[i]);end;end;while(len>1)and(c.s[len]=0) do dec(len);c.len:=len;end;procedure main;beginDivide(x[1],x[2],y,w);end;procedure out;beginassign(output,fn_out);rewrite(output);PrintHP(y);writeln;PrintHP(w);writeln;close(output);end;begininit;main;out;end.第三章排列与组合3.1加法原理与乘法原理做一件事情，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有 m2种不同的方法，……，在第n类办法中有 m n种不同的方法。