Unit AritUnit;                                    { aritunit.pas; 91.07.01. }

                                          { nagypontoss gu eg‚sz-aritmetika }
  Interface
    {
                          Alaparitmetika modul:
        Eljarasok:
            Nulla_e(a: Szam): Boolean
            Nagyobb(a,b:Szam): Boolean;
            Novel(mit:Szam);
            Osszead(a,b,osszeg: Szam)
            Kivon(a,b,kulonbseg: Szam)
            Szoroz(a,b,szorzat: Szam)
            Oszt(a,b,hanyados,maradek: Szam)
            AlapSzoroz(a: Szam, kitevo: Egesz, szorzat: Szam)
        Tipusok:
            Szamjegy
            PozSzam
            EgeszSzam
            VegyesalapuEgesz
        Valtozok:
             Nulla - val˘j ban konstans
             Egy   - val˘j ban konstans
             Plusz
             Szor
             Pontossag
             Tulcsordult
        Konstansok:
             MaxPontossag
             Nulla - val˘j ban konstans
             Egy
             Ketto
    }

    Uses
        Crt;

    Const
        MaxPontossag=255;
    Var
        Pontossag : Integer;
    Type
        Szamjegy         = Byte;
        PozSzam          = Array [0..MaxPontossag+1] of Szamjegy;
        SzamrendszerTipus= 2..256;
        PontossagTipus   = 0..MaxPontossag+1;
        ElojelTipus      = (Poz,Neg);
        EgeszSzam        = Record
                             elojel      : ElojelTipus;
                             hossz       : PontossagTipus;
                             szamrendszer: SzamrendszerTipus;
                             jegy        : PozSzam;
                           End;
        VegyesalapuEgesz = Record
                             elojel      : ElojelTipus;
                             hossz       : 0..MaxPontossag;
                             alapok      : Pozszam;
                             jegy        : PozSzam;
                            End;

    Var
       Nulla,Egy,
       Ketto       : EgeszSzam;
       Plusz,Szor  : longInt;
       Tulcsordult : Boolean;

    Procedure Beolvasas(var a: EgeszSzam; kerdes: String);
    Procedure Kiiras(a: EgeszSzam; szoveg: String);
    Function  Nulla_e(var x: EgeszSzam): Boolean;
    Procedure Novel(Var n: EgeszSzam);
    Procedure Osszead(var a,b,osszeg: EgeszSzam);
    Procedure Kivon(var a,b,kulonbseg: EgeszSzam);
    Procedure Szoroz(var a,b,szorzat: EgeszSzam);
    Procedure Oszt(var a,b,hanyados,maradek: EgeszSzam);
    Procedure AlapSzoroz(var a: EgeszSzam; kitevo: Integer; var szorzat: EgeszSzam);
    Function  Nagyobb(var a,b: EgeszSzam): Boolean;

    Function Min(x,y: Integer): Integer;
    Function Max(x,y: Integer): Integer;

  Implementation

  Var
     Szamrendszer: SzamrendszerTipus;

  Procedure Beolvasas(var a: EgeszSzam; kerdes: String);
    var
       i: Integer;
       s: String;
  begin
    i:=0; a:=Nulla;
    write(kerdes,'?'); Readln(s);
    if (s[1]<>'+') and (s[1]<>'-') then s:='+'+s;
    for i:=0 to Length(s)-2 do a.jegy[i]:=ord(s[Length(s)-i])-ord('0');
    a.hossz:=Length(s)-2;
    if s[1]='+' then
        a.elojel:=Poz
    else
       a.elojel:=Neg;
    a.Szamrendszer:=10;
  end;

  Procedure Kiiras(a: EgeszSzam; szoveg: String);
    var
       i,n: Integer;
  begin
    if szoveg<>'' then write(szoveg,':');
    if a.elojel=Neg then write('-');
    for i:=a.hossz downto 0 do write(a.jegy[i]:1);
    writeln;
  end;

  Function Max(x,y: Integer): Integer;
  Begin
    If x>y then Max:=x else Max:=y
  End; { Max }

  Function Min(x,y: Integer): Integer;
  Begin
    If x<y then Min:=x else Min:=y
  End; { Min }

  Procedure Inicializalas;
    var
       i: Integer;
  begin
    Pontossag:=200;
    for i:=0 to MaxPontossag do Nulla.jegy[i]:=0;
    Nulla.hossz:=0;
    Nulla.elojel:=Poz;
    Nulla.szamrendszer:=10;
    Egy:=Nulla;   Egy.jegy[0]:=1;
    Ketto:=Nulla; Ketto.jegy[0]:=2;
    Tulcsordult:=False
  end;

  Procedure Szamrendszer_hiba(sz1,sz2: integer);
  begin
    writeln('Kulonbozo szamrendszerek:',sz1:3,sz2:3);
  end;

  Procedure Tulcsordulas;
  begin
{    Writeln('Tulcsordulas!!!');}
    Tulcsordult:=True;
  end;

  Function Nulla_e(var x: EgeszSzam): Boolean;
    Var
       i: Integer;
  begin
    i:=0; while (i<=x.hossz) and (x.jegy[i]=0) do i:=i+1;
    Nulla_e:=(i>x.hossz)
  end;

  Procedure Hosszallitas(var x: EgeszSzam; honnan: Integer);
    var
       d: Integer;
  begin
    If honnan<MaxPontossag then d:=honnan else d:=MaxPontossag;
    while (d>0) and (x.jegy[d]=0) do d:=d-1;
    x.hossz:=d;
  end;

  Procedure Novel(Var n: EgeszSzam);
    Var
       i,atvitel,c : Integer;
  Begin
    atvitel:=1; { atvitel = a +1 }
    For i:=0 to n.hossz do
    Begin
      c:=(n.jegy[i]+atvitel) mod n.szamrendszer;
      atvitel:=(n.jegy[i]+atvitel) div n.szamrendszer;
      n.jegy[i]:=c
    End;
                                                       Plusz:=n.hossz+1;
                                                       Szor:=2*n.hossz+2;
    If (n.hossz=MaxPontossag) and (atvitel>0) then
                      Tulcsordult:=True  else if
       atvitel>0 then
                      Begin
                        Inc(n.hossz); n.jegy[n.hossz]:=1
                      End
    {End If}
  End; { Novel }

  Procedure Osszeadas(var a,b,osszeg: PozSzam; h: integer);
    var
       i,atvitel: Integer;
  begin
    If Tulcsordult then Exit;
    atvitel:=0;
    for i:=0 to h do
    begin
      osszeg[i]:=(a[i]+b[i]+atvitel) mod Szamrendszer;
      atvitel:=(a[i]+b[i]+atvitel) div Szamrendszer;
    end;
    if (MaxPontossag=h) and (atvitel>0) then Tulcsordulas
                                        else osszeg[h+1]:=atvitel;
  end;

  Function Nagyobb(var a,b: EgeszSzam): Boolean;
    var
       i   : Integer;
       nagy: Boolean;
  begin
    nagy:=a.hossz>b.hossz;
    if a.hossz=b.hossz then
    begin
      i:=a.hossz;
      while (i>0) and (a.jegy[i]=b.jegy[i]) do i:=i-1;
      nagy:=(a.jegy[i]>=b.jegy[i]);
    end;
    nagyobb:=nagy;
  end;

  Procedure Ossze(var a,b,osszeg: EgeszSzam);
    var
       i,h: Integer;
  begin
    if a.hossz>b.hossz then
    begin
      h:=a.hossz;
      for i:=b.hossz+1 to h do b.jegy[i]:=0;
    end
        else
    begin
      h:=b.hossz;
      for i:=a.hossz+1 to h do a.jegy[i]:=0;
    end;
    Osszeadas(a.jegy,b.jegy,osszeg.jegy,h);
    osszeg.elojel:=a.elojel;
    Hosszallitas(osszeg,h+1);
                                         Plusz:=osszeg.hossz; Szor:=0;
  end;

  Procedure Kivonas(var a,b,kulonbseg: PozSzam; h: integer);
    var
       i,atvitel,x: Integer;
  begin
    If Tulcsordult then Exit;
    atvitel:=0;
    for i:=0 to h do
    begin
      x:=a[i]-b[i]-atvitel;
      if x<0 then begin kulonbseg[i]:=x+Szamrendszer; atvitel:=1 end
             else begin kulonbseg[i]:=x; atvitel:=0 end;
    end;
  end;

  Procedure Ki(var a,b,kulonbseg: EgeszSzam);
    var
       i,d    : Integer;
  begin
     if nagyobb(a,b) then
     begin
       for i:=b.hossz+1 to a.hossz do b.jegy[i]:=0;
       Kivonas(a.jegy,b.jegy,kulonbseg.jegy,a.hossz); kulonbseg.elojel:=Poz;
                                              Plusz:=a.hossz; Szor:=0;
     end
     else
     begin
       for i:=a.hossz+1 to b.hossz do a.jegy[i]:=0;
       Kivonas(b.jegy,a.jegy,kulonbseg.jegy,b.hossz); kulonbseg.elojel:=Neg;
                                              Plusz:=b.hossz; Szor:=0;
     end;
     Hosszallitas(kulonbseg,Max(a.hossz,b.hossz));
  end;

  Procedure Osszead(var a,b,osszeg: EgeszSzam);
    var
       d: Integer;
  begin
    Szamrendszer:=a.szamrendszer;
    if Szamrendszer<>b.szamrendszer
                     then Szamrendszer_hiba(a.szamrendszer,b.szamrendszer)
                     else osszeg.szamrendszer:=Szamrendszer;
    if        a.elojel=b.elojel                then  Ossze(a,b,osszeg)
    else if  (a.elojel=Poz) and (b.elojel=Neg) then  Ki(a,b,osszeg)
    else {if (a.elojel=Neg) and (b.elojel=Poz) then} Ki(b,a,osszeg)
  end;

  Procedure Kivon(var a,b,kulonbseg: EgeszSzam);
    var
       d: Integer;
  begin
    Szamrendszer:=a.szamrendszer;
    if Szamrendszer<>b.szamrendszer
                     then Szamrendszer_hiba(a.szamrendszer,b.szamrendszer)
                     else kulonbseg.szamrendszer:=Szamrendszer;
    if       (a.elojel=Poz) and (b.elojel=Poz) then  Ki(a,b,kulonbseg)
    else if   a.elojel<>b.elojel               then  Ossze(a,b,kulonbseg)
    else {if (a.elojel=Neg) and (b.elojel=Neg) then} Ki(b,a,kulonbseg);
  end;

  Procedure Szoroz(var a,b,szorzat: EgeszSzam);
    var
       i,d,j,k,
       n,m,iv,ik    : Integer;
       tul          : Boolean;
  begin
    If Tulcsordult then Exit;
    Szamrendszer:=a.szamrendszer;
    if Szamrendszer<>b.szamrendszer
                     then Szamrendszer_hiba(a.szamrendszer,b.szamrendszer)
                     else szorzat.szamrendszer:=Szamrendszer;
    d:=0; tul:=false; k:=0;
                                                   Plusz:=0; Szor:=0;
    while (k<=a.hossz+b.hossz+1) and not tul do
    begin
      if (k>MaxPontossag) and (d<>0) then tul:=true
         else begin
                if k>b.hossz then ik:=k-b.hossz else ik:=0;
                if k<a.hossz then iv:=k else iv:=a.hossz;
                for i:=ik to iv do d:=d+a.jegy[i]*b.jegy[k-i];
                                                   Plusz:=Plusz+iv-ik+1;
                                                   Szor:=Szor+iv-ik+1;
                szorzat.jegy[k]:=d mod Szamrendszer; d:=d div Szamrendszer;
                                                   Szor:=Szor+2;
              end;
      k:=k+1;
    end;
    Hosszallitas(szorzat,a.hossz+b.hossz+1);
    if (a.elojel=b.elojel) or nulla_e(szorzat)
                           then szorzat.elojel:=Poz else szorzat.elojel:=Neg;
    if tul then Tulcsordulas;
  end;

  Procedure AlapSzoroz(var a: EgeszSzam; kitevo: Integer; var szorzat: EgeszSzam);
    Var
       tul     : Boolean;
       k,meddig: Integer;
  Begin
    If Tulcsordult then Exit;
    Szamrendszer:=a.szamrendszer;
    szorzat.elojel:=a.elojel;
    szorzat.szamrendszer:=Szamrendszer;
    tul:=(a.hossz+kitevo>MaxPontossag);
                                                   Plusz:=0; Szor:=0;
    If Not tul then {nincs tulcsordul s}
      If kitevo>0 then
      Begin {szorz s az alapsz m-hatv nnyal: jobbra l‚ptet‚s}
        If a.hossz+kitevo>MaxPontossag then
               meddig:=MaxPontossag-kitevo
            else
               meddig:=a.hossz;
        For k:=MaxPontossag downto meddig+kitevo+1 do szorzat.jegy[k]:=0;
        For k:=meddig downto 0 do szorzat.jegy[k+kitevo]:=a.jegy[k];
        For k:=0 to kitevo-1 do szorzat.jegy[k]:=0;
        szorzat.hossz:=a.hossz+kitevo
      End
        else
      Begin {oszt s az alapsz m-hatv nnyal: balra l‚ptet‚s}
        For k:=-kitevo to a.hossz do szorzat.jegy[k+kitevo]:=a.jegy[k];
        For k:=MaxPontossag downto a.hossz+kitevo+1 do szorzat.jegy[k]:=0;
        szorzat.hossz:=a.hossz+kitevo
      End
    else
      Tulcsordulas
  End;

  Procedure Oszt(var a,b,hanyados,maradek: EgeszSzam);
    var
       i,n,m,j,x: Integer;
       seged    : EgeszSzam;
       norm,at  : Integer;

    Procedure Normalas(var a,b,na,nb: EgeszSzam; var norm: Integer);
      var
         jegy   : Szamjegy;
         i,d1,d2: Integer;
    begin
      na:=a; nb:=b; norm:=Szamrendszer div (nb.jegy[nb.hossz]+1);
      if norm>1 then
      begin
        d1:=0;
        for i:=0 to na.hossz do
        begin
          d2:=na.jegy[i]*norm+d1;
          na.jegy[i]:=d2 mod Szamrendszer;
          d1:=d2 div Szamrendszer;
        end;
        na.jegy[na.hossz+1]:=d1; na.hossz:=na.hossz+1;
                                               Szor:=Szor+3*(na.hossz+1);
        d2:=0;
        for i:=0 to nb.hossz do
        begin
          d1:=nb.jegy[i]*norm+d2;
          nb.jegy[i]:=d1 mod Szamrendszer;
          d2:=d1 div Szamrendszer;
        end;
                                               Szor:=Szor+3*(nb.hossz+1);
      end
          else
      begin
        na.jegy[na.hossz+1]:=0; na.hossz:=na.hossz+1;
      end;

    end;

    Procedure Egyjegyosztas(var osztando,oszto: EgeszSzam; var h:Szamjegy);
      var
         n,m,i,d,x: Integer;
         q      : Szamjegy;
         seged  : PozSzam;
         nagy   : Boolean;
    begin
       n:=osztando.hossz; m:=oszto.hossz;
       {
                  a hanyados becslese
       }
       if osztando.jegy[n]=oszto.jegy[m] then q:=Szamrendszer-1
          else begin
               q:=(Szamrendszer*osztando.jegy[n]+osztando.jegy[n-1])
                         div oszto.jegy[m];
                                             Szor:=Szor+2; Plusz:=Plusz+1;
               end;
       {
                  a becsles gyors javitasa
       }
       if m>0 then while oszto.jegy[m-1]*q>(Szamrendszer*osztando.jegy[n]
                         +osztando.jegy[n-1]-q*oszto.jegy[m])*Szamrendszer
                         +osztando.jegy[n-2] do begin
                                                 q:=q-1;
                                                 Szor:=Szor+4; Plusz:=Plusz+3;
                                                end;
       {
                  a becsles ellenorzese es javitasa
       }
       repeat
         d:=0;
         for i:=0 to m do
         begin
           seged[i]:=(oszto.jegy[i]*q+d) mod Szamrendszer;
           d:=(oszto.jegy[i]*q+d) div Szamrendszer
         end;
                                    Szor:=Szor+3*(m+1); Plusz:=Plusz+2*(m+1);
         seged[m+1]:=d;
         nagy:=(d=0);
         if d<>0 then
         begin
           i:=m+1;
           while (i>0) and (osztando.jegy[n-m-1+i]=seged[i]) do i:=i-1;
           nagy:=(osztando.jegy[n-m-1+i]>=seged[i]);
         end;
         if not nagy then q:=q-1;
       until nagy;
       h:=q;
       d:=0;
       for i:=0 to m+1 do
       begin
         x:=osztando.jegy[n-m-1+i]-seged[i]-d;
         if x<0 then begin x:=x+Szamrendszer; d:=1 end else d:=0;
         osztando.jegy[n-m-1+i]:=x;
       end;
                                               Plusz:=Plusz+m+2;
       osztando.hossz:=osztando.hossz-1;
    end;

  begin
    Hanyados:=Nulla;
    If Tulcsordult then Exit;
    Szamrendszer:=a.szamrendszer;
    if Szamrendszer<>b.szamrendszer
                     then Szamrendszer_hiba(a.szamrendszer,b.szamrendszer)
                     else begin
                            hanyados.szamrendszer:=Szamrendszer;
                            maradek.szamrendszer:=Szamrendszer;
                          end;

                                               Plusz:=0; Szor:=0;
    if Nulla_e(b) then Tulcsordulas
       else if not Nagyobb(a,b) then
            begin
              hanyados:=Nulla; maradek:=a;
            end
            else
            begin
              if a.hossz<=MaxPontossag then Normalas(a,b,maradek,seged,norm)
              else
                begin
                  maradek:=a;
                  seged:=b;
                  Norm:=1;
                end;
              j:=maradek.hossz;
              for i:=j downto b.hossz+1 do
                Egyjegyosztas(maradek,seged,hanyados.jegy[i-b.hossz-1]);
              for i:=MaxPontossag downto j-b.hossz do hanyados.jegy[i]:=0;
              Hosszallitas(hanyados,j-b.hossz);
              j:=seged.hossz;
              at:=0;
              for i:=j downto 0 do
              begin
                x:=(at*Szamrendszer+maradek.jegy[i]);
                maradek.jegy[i]:=x div norm; at:=x mod norm;
              end;
              Hosszallitas(maradek,b.hossz+1);
              if (a.elojel=b.elojel) or nulla_e(hanyados)
                 then hanyados.elojel:=Poz
                 else hanyados.elojel:=Neg;
              if nulla_e(maradek) then maradek.elojel:=Poz
                                  else maradek.elojel:=a.elojel;
            end;
  end;

begin
  Inicializalas;
end.