高精度无敌大全.doc

衡阳市八中Oi队高精度无敌大全 By 皮一凡 PM 1:感谢PYF的辛勤付出 2:请大家多加试验，如有问题及时提出以便修正 编号 名称 程序 样例程序及练习题 1 高精度数的定义 type bignum = array[0..Maxlen] of longint; {位数根据题目估计} const ra = 10000; {万进制，即4位一存} {8位一存改成100000000即可} 2 比较大小 function bigger(a , b : bignum ) : boolean; {如a=b返回true，反之返回false} var i : longint; begin if a[0] b[0] then exit( true ); if a[0] b[0] then exit( false ); for i := a[0] downto 1 do begin if a[i] b[i] then exit( true ); if a[i] b[i] then exit( false ); end; bigger := true; end; { bigger } 3 高精度加法 procedure add( a , b : bignum; var c : bignum ); var i , Len : longint; begin fillchar( c , sizeof( c ) , 0 ); if a[0] b[0] then Len := a[0] else Len := b[0]; for i := 1 to Len do begin inc( c[i] , a[i] + b[i] ); if c[i] = ra then begin inc( c[i + 1] ); dec( c[i] , ra ); end; end; if c[Len + 1] 0 then inc( Len ); c[0] := Len; end; { add } 参考练习题: Zju1828 Fibonacci Numbers 样例程序 4 高精度减法 {减法注意小数减大数要加负号} procedure sub( a , b : bignum; var c : bignum ); var i , Len : longint; begin fillchar( c , sizeof( c ) , 0 ); if a[0] b[0] then Len := a[0] else Len := b[0]; for i := 1 to Len do begin inc( c[i] , a[i] - b[i] ); if c[i] 0 then begin dec( c[i + 1] ); inc( c[i] , ra ); end; end; while ( Len 1 ) and ( c[Len] = 0 ) do dec( Len ); c[0] := Len; end; { sub } SGU112需要用到高精度减法 5 高精度乘以低精度 procedure Low_multi( a : bignum; b : longint; var c : bignum ); var i , Len : longint; begin fillchar( c , sizeof( c ) , 0 ); Len := a[0]; for i := 1 to Len do begin inc( c[i] , a[i] * b ); {多位一存注意溢出} inc( c[i + 1] , c[i] div ra ); c[i] := c[i] mod ra; end; inc( Len ); //不要遗漏 while c[Len] = ra do {处理最高位的进位} begin c[Len + 1] := c[Len] div ra; c[Len] := c[Len] mod ra; inc( Len ); end; while ( Len 1 )