Làm việc với số cực lớn

[hung06061995]

Mình cần công thức tính cộng và nhân với các số trên chuỗi. Ví dụ chuỗi '34' + '54' ='88' hay '23'*'3'='69'
Mình có bài phép cộng nhưng hơi dài, các bạn tham khảo và tìm cách làm ngắn hơn:

function plus(a,b:string):string;
var
   s1,s2,du,i,j:byte;
   code:integer;
   k,k1:string;
begin
        plus:=''; k:=''; du:=0;
        i:=length(a); j:=length(b);
        while (i>0) and (j>0) do
              begin
                   s1:=0; s2:=0;
                   val(a[i],s1,code);
                   val(b[j],s2,code);
                   str((s1+s2+du) mod 10 ,k1);
                   du:=(s1+s2+du) div 10;
                   k:=k+k1; i:=i-1; j:=j-1;
              end;
        if (i=0) and (j<>0) then
          while j>0 do
           begin
                val(b[j],s2,code);
                str((s2+du) mod 10 ,k1);
                du:=(s2+du) div 10;
                k:=k+k1; j:=j-1;
           end
        else if (j=0) and (i<>0) then
          while (i>0)  do
           begin
                val(a[i],s1,code);
                str((s1+du) mod 10 ,k1);
                du:=(s1+du) div 10;
                k:=k+k1; i:=i-1;
           end
          else
            begin
              str(du,k1);
              k:=k+k1;
            end;
          k1:='';
        for i:=length(k) downto 1 do k1:=k1+k[i];
        plus:=k1;
end;

[nhat_truong]

function Congsl(st1,st2:string):string;
    var i,so1,so2,nho:byte;
        sai:integer;
        kq,tam:string;
    begin
      nho:=0; kq:='';
      while length(st2)<length(st1) do st2:='0'+st2;
      while length(st2)>length(st1) do st1:='0'+st1;
      for i:= length(st2) downto 1 do
          begin
               val(st1[i],so1,sai);
               val(st2[i],so2,sai);
               str((so1+so2+nho) mod 10,tam);
               kq:=tam+kq;
               nho:=(so1+so2+nho) div 10;
          end;
      if nho<>0 then
         begin
              str(nho,tam);
              kq:=tam+kq;
         end;
      congsl:=kq;
    end;

function nhan_xau_so(st1,st2:string):string;
    var i,so1,so2,nho:byte;
        sai:integer;
        kq,tam:string;
    begin
      nho:=0; val(st2[1],so2,sai);
      kq:='';
      for i:= length(st1) downto 1 do
          begin
               val(st1[i],so1,sai);
               str((so1*so2+nho) mod 10,tam);
               kq:=tam+kq;
               nho:=(so1*so2+nho) div 10;
          end;
      if nho<>0 then
         begin
              str(nho,tam);
              kq:=tam+kq;
         end;
      nhan_xau_so:=kq;
    end;

function Nhansl (st1,st2:string):string;
    var i:byte;
        kq:string;
    begin
      kq:='';
      for i:=1 to length(st2) do
          begin
               kq:=congsl(kq+'0',nhan_xau_so(st1,st2[i]));
          end;
      Nhansl:=kq;
    end;

[MMKC_IT]

Program solon;
Const  f1='';
        f2='';
        hecoso=10000;
        nmax=510;
Type    DigitType = longint;
        Bignum = array[0..nmax] of DigitType;
Var     fi,fo:text;
        A,B,C,D:bignum;
        atmp:array[-9..nmax*2] of integer;

        Procedure Input;
        Var    i,so,j:integer;
                ch:char;
        Begin
                Assign(fo,f1);reset(fo);
                i:=0;
                While not(eoln(fo)) do
                Begin
                        read(fo,ch);
                        inc(i);
                        so:=ord(ch)-ord('0');
                        atmp[i]:=so;
                end;
                A[0]:=(i-1) div 4 +1;j:=i;i:=1;
                While i<=a[0] do
                begin
                    a[i]:=atmp[j-3]*1000+atmp[j-2]*100+atmp[j-1]*10+atmp[j];
                    inc(i);dec(j,4);
                end;
                readln(fo);i:=0;
                While not(eoln(fo)) do
                Begin
                        read(fo,ch);
                        inc(i);
                        so:=ord(ch)-ord('0');
                        atmp[i]:=so;
                end;
                b[0]:=(i-1) div 4 +1;j:=i;i:=1;
                While i<=b[0] do
                begin
                    b[i]:=atmp[j-3]*1000+atmp[j-2]*100+atmp[j-1]*10+atmp[j];
                    inc(i);dec(j,4);
                end;
                Close(fo);
        end;

        Procedure Output;
        Var    i:integer;
                st:string;
        Begin
                write(fi,c[c[0]]);
                For  i:=c[0]-1 downto 1 do
                Begin
                        str(c[i],st);
                        While length(st)<4 do st:='0'+st;
                write(fi,st);
                end;
                writeln(fi);
        end;

        Procedure Plus(A,B:bignum;var c:bignum);
        Var    i,nho:integer;
        Begin
                nho:=0;c[0]:=a[0];
                If a[0]<b[0] then c[0]:=b[0];
                For i:=1 to c[0] do
                begin
                        c[i]:=a[i]+b[i]+nho;
                        nho:=c[i] div hecoso;
                        c[i]:=c[i] mod hecoso;
                end;
                If nho>0 then
                begin
                        inc(c[0]);c[c[0]]:=nho;
                end;
        end;

        Procedure Minus(A,B:bignum;var  C:bignum);
        Var    nho,i:integer;
        Begin
                nho:=0;c[0]:=a[0];
                For i:=1 to a[0] do
                begin
                        c[i]:=a[i]-b[i]-nho;
                        If c[i]<0 then
                        begin
                                c[i]:=c[i]+hecoso;nho:=1;
                        end
                        else nho:=0;
                end;
                While (C[c[0]]=0) and (c[0]>1) do dec(c[0]);
        end;

        Procedure Multimin(x:longint);
        Var    nho,p:qword;
                i:integer;
        Begin
                nho:=0;d[0]:=a[0];p:=0;
                For i:=1 to a[0] do
                begin
                        p:=a[i]*x+nho;
                        nho:=p div hecoso;
                        d[i]:=p mod hecoso;
                end;
                While nho>0 do
                begin
                        inc(d[0]);
                        d[d[0]]:= nho mod hecoso;
                        nho:=nho div hecoso;
                end;
        end;

        Procedure Chuyen(var d:bignum;k:integer);
        Var    i:integer;
        Begin
                If (d[0]=1) and (d[1]=0) then d[0]:=d[0]+k-1
                else d[0]:=d[0]+k;
                For i:=d[0] downto 1 do
                If i>k then d[i]:=d[i-k]
                else d[i]:=0;
        end;


        Procedure Multimax;
        Var    i:integer;
        begin
                For i:=1 to b[0] do
                begin
                    multimin(b[i]);
                    chuyen(d,i-1);
                    plus(C,D,C);
                end;
        end;

        Function Compare(A,B:bignum):byte;
        Var    i:integer;
        Begin
                If a[0]<b[0] then begin compare:=1;exit;end;
                If a[0]>b[0] then begin compare:=3;exit;end;
                For i:=a[0] downto 1 do begin
                        If a[i]<b[i] then begin compare:=1;exit;end;
                        If a[i]>b[i] then begin compare:=3;exit;end;
                end;
                Compare:=2;
        end;

        Procedure Process;
        Begin
                Plus(a,b,c);output;
                If (compare(a,b)=1) or (compare(a,b)=2) then
                begin
                        Minus(b,a,c);
                        If c[c[0]]<>0 then write(fi,'-');
                end
                else minus(a,b,c);output;
                Fillchar(c,sizeof(c),0);
                Multimax;output;
        end;

Begin
        Input;
        Assign(fi,f2);rewrite(fi);
        process;
        Close(fi);
end.

Cộng trừ nhân với số cực lớn hơn cả string

[linhhahaduc]

hay quá, cách này dùng thêm hệ cơ số nên tăng tốc độ lên khá nhiều
Thanks anh MMKC_IT ^^

[lqhuy93]

chú ý kiểu bigint này không nhập xuất được từ màn hình mà qua trung gian string

[technolt]

Cài thế này nhanh j` nhỉ?
1) Ko cài số lớn = string, cài = mảng và lưu lại các chữ số theo thứ tự ngược
2) Ko cộng cơ số 10, cộng với cơ số 10^to hơn. VD: 10^9

Như vậy mới tăng tốc được
Cài thế này rất nhiều bài sẽ bị TLE

[mr_invincible]

Free Pascal nếu chỉ có cộng trừ thì code hẳn cơ số 10^15 -> 10^18
chú ý quan trọng hơn là phép div mod hoạt động chậm. Nếu cộng trừ thôi thì nên đổi thành toàn các phép + -

[technolt]

anh biết div số lớn ko?
hôm thi IPSC em ko biết cài và đến h vẫn ko biết +_+

[mr_invincible]

Có. div, khai căn... : chặt nhị phân.

[mofceoma]

Xủ lí 510 số? Có bài BIGNUM cần xử lí đến nghìn số đó anh.Cài đặt bằng xâu thì dễ nhưng Max thì cũng dc 256.Theo em nên tính theo hệ nhị phân rồi chuyển qua thập phân là hay nhất.Anh nào cài đặt dùm em với. Thanks!