//Данный модуль содержит набор функций/процедур для работы с большими числами в q-ичной системе счисления:
unit LongNumber;

{$mode objfpc}

interface
uses sysutils;
const
	MIN_BASE = 2; MAX_BASE = 36;
   //Q: QWord = 1 shl 32;
   Q = 10;
type
	//Тип длинного целого:
	TLongNumber = record
		dig: array of QWord;	//Буфер, хранящий в себе цифры числа;
		inv: boolean;		//Знак числа: (+) true, (-) false;
	end;

	TBase = MIN_BASE..MAX_BASE;


	//Формирует длинное число на основе его строкового представления в заданной системе счисления:
	function fromString(const str: AnsiString; base: TBase): TLongNumber;

	//Формирует строковое представление длинного числа в заданной системе счисления:
	function toString(const val: TLongNumber; base: TBase): AnsiString;

	//Присваивает длинному числу значение короткого:
	operator:= (val: int64) res: TLongNumber;

	//Деление длинного на короткое (возвращает целую часть, в последний аргумент записывает остаток):
	function divmod(const lhs: TLongNumber; rhs: int32;
	                                   out rem: uint32): TLongNumber;
	//Деление длинного на короткое (возвращает целую часть):
	operator / (const lhs: TLongNumber; rhs: int32) ans: TLongNumber;
	//Умножение длинного на короткое:
	operator * (const lhs: TLongNumber; rhs: int32) ans: TLongNumber;
	//Умножение короткого на длинное:
	operator * (lhs: int32; const rhs: TLongNumber) ans: TLongNumber;
	//Умножение длинных чисел:
	operator * (const lhs, rhs: TLongNumber) ans: TLongNumber;
	//Сложение длинных чисел:
	operator + (const lhs, rhs: TLongNumber) ans: TLongNumber;
	//Разность длинных чисел:
	operator - (const lhs, rhs: TLongNumber) ans: TLongNumber;
	//Унарный минус:
	operator - (const val: TLongNumber) ans: TLongNumber;

	//Меньше либо равно:
	operator <= (const lhs, rhs: TLongNumber) ans: boolean;
	//Больше либо равно:
	operator >= (const lhs, rhs: TLongNumber) ans: boolean;
	//Не равно:
	operator <> (const lhs, rhs: TLongNumber) ans: boolean;
	//Меньше:
	operator < (const lhs, rhs: TLongNumber) ans: boolean;
	//Больше:
	operator > (const lhs, rhs: TLongNumber) ans: boolean;
	//Равно:
	operator = (const lhs, rhs: TLongNumber) ans: boolean;

implementation
 const
     alph36 = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';

function CompareModule(lhs, rhs: TLongNumber): boolean;
var i: integer;
begin
     if (high(lhs.dig) > high(rhs.dig)) then begin
        Result := true;
     end
     else if (high(rhs.dig) > high(lhs.dig)) then begin
           Result := false;
     end
     else if (high(rhs.dig) = high(lhs.dig)) then begin
          for i:=high(lhs.dig) downto 0 do begin
              if (lhs.dig[i]) > (rhs.dig[i]) then begin
                 Result := true;
                 exit;
              end;
              if (lhs.dig[i] < rhs.dig[i]) then begin
                 Result := false;
                 exit;
              end;
          end;
          Result := false;
     end;
end;
function CharToLongNumber(val: char; base: TBase): TLongNumber;
var num: int64;
begin
	num := Pos(val, alph36);
  if (num > 0) and (num-1 < base)  then begin
  	Result := num-1;
	end
  else
  raise Exception.Create('Invalid char ''' + val + '''');

end;

function fromString(const str: AnsiString; base: TBase): TLongNumber;
var i, n: integer;
   res, c: TLongNumber;
begin
  res := 0;
  if str = '' then exit(res);
  if (str = '0') or (str = '-0') then res.inv := true;
  if (str[1] = '-') then begin
    // res.inv := false;
     n := 2;
  end
  else begin
     //  res.inv := true;
       n :=  1;
  end;
  res.inv := true;
  while((str[n] = '0') and (n < Length(str))) do n+=1;

  for i:=n to length(str) do begin
      c := charToLongNumber(str[i], base);
      //c := StrToLongNumber(str[i], base);
      Res := Res * base + c;
  end;
  if (str[1] = '-') then begin
     res.inv := false;

end;
  exit(res);

end;
function Invers_str(str: AnsiString): AnsiString;
var newS: AnsiString;
i: integer;
begin
	for i:=length(str) downto 1 do begin
 		newS += str[i];
  end;
  Result := newS;
end;

function toString(const val: TLongNumber; base: TBase): AnsiString;
var res, buf: TLongNumber;
   c: longWord;
begin
  Result := '';
  res := val;
  buf := base;

  while (CompareModule(res,buf)) do begin
  	res := divmod(res, base, c);
    Result += IntToStr(c);
  end;
  res := divmod(res, base, c);
  Result += IntToStr(c);
  if (res.dig[0] <> 0) then result += IntToStr(res.dig[0]);
  if (res.inv = false) then begin
  	Result += '-';
  end;
  Result := invers_str(result);
end;

operator := (val: int64) res: TLongNumber;
begin
	SetLength(res.dig, 1);
  res.dig[0] := abs(val);
  if (val >= 0) then begin
     res.inv := true;
  end
  else res.inv := false;
end;


function divmod(const lhs: TLongNumber; rhs: int32; out rem: uint32): TLongNumber;
var buf: QWord;
   i, zcount: integer;
begin
      rem := 0;
      buf := 0;
     if (rhs = 0) then begin
				raise Exception.Create('DIV BY ZERO');
     end;
     if ((rhs > 0) and (lhs.inv = true)) or ((rhs < 0) and (lhs.inv = false)) then Result.inv := true
     else Result.inv := false;
     if (rhs < 0) then rhs *= -1;
     SetLength(Result.dig, high(lhs.dig)+1);
     for i := high(Result.dig) downto 0 do begin
         buf := rem * Q + lhs.dig[i];
         Result.dig[i]:= buf div rhs;
         rem := buf mod rhs;
     end;
     zcount := 0;
     for i := high(Result.dig) downto 1 do begin
         if (result.dig[i] = 0) then zcount += 1
         else break;
     end;
     if zcount > 0 then begin
        Setlength(result.dig, length(result.dig) - zcount);
     end;


end;

operator / (const lhs: TLongNumber; rhs: int32) ans: TLongNumber;
var rem: Uint32;
   i: integer;
begin
		Result := divmod(lhs, rhs, rem);
end;
function Mult(lhs: TLongNumber; b: Int32): TLongNumber;
var
c: QWord;
buf: QWOrd;
i: integer;
begin
      c := 0;
      SetLength(Result.dig, high(lhs.dig)+1);
     for i:=0 to high(Result.dig) do begin
         buf := lhs.dig[i] * b + c;
         c := buf div Q;
         Result.dig[i] := buf mod Q;
     end;
     if (c > 0) then begin
        SetLength(Result.dig, high(Result.dig)+2);
        Result.dig[i+1] := c;
     end;
end;
operator * (const lhs: TLongNumber; rhs: int32) ans: TLongNumber;
var b:integer;
begin
     if (rhs <> 0) then begin
        if ((rhs > 0) and (lhs.inv = true)) or ((rhs < 0) and (lhs.inv = false)) then begin
           Result.inv := true;
        end
        else Result.inv := false;
     end
     else begin
         Result.inv := true;
     end;
     if (rhs < 0) then begin
        b := rhs * -1;
     end
     else b := rhs;
     Result := Mult(lhs, b);
end;

operator * (lhs: int32; const rhs: TLongNumber) ans: TLongNumber;
begin
     Result := rhs * lhs;
end;

operator * (const lhs, rhs: TLongNumber) ans: TLongNumber;
var i, j: integer;
s, buf1, buf2: QWord;
a, b: TLongNumber;
begin
  	 a.dig := copy(lhs.dig);
     b.dig := copy(rhs.dig);
     a.inv := lhs.inv;
     b.inv := rhs.inv;
     s := 0;
     if (a.dig[0] = 0) and (a.inv = false) then begin
     	a.inv :=true;
     end;
     if (b.dig[0] = 0) and (b.inv = false) then begin
     	b.inv :=true;
     end;
     if (a.inv = b.inv) then
        Result.inv := true
     else
         Result.inv := false;
     if (a = 0) or (b = 0) then begin
        Result := 0;
        exit;
     end
     else begin
     		SetLength(Result.dig, high(a.dig) + high(b.dig) + 1);
        for i:=0 to high(Result.dig) do begin
        		Result.dig[i] := 0;
        end;
        for i:=0 to high(b.dig) do begin
            s := 0;
        		for j:=0 to high(a.dig) do begin
            		buf1 := b.dig[i] * a.dig[j];
                 buf2 := Result.dig[i+j] + s;
             		s := buf1 div Q + buf2 div Q + (buf1 mod Q + buf2 mod Q) div Q;
                Result.dig[i+j] := ((buf1 mod Q) + (buf2 mod Q)) mod Q;
            end;
            if (s > 0) then begin
            		if i = high(b.dig) then SetLength(Result.dig, Length(Result.dig) + 1);
                Result.dig[i + high(a.dig) + 1] := s;
            end;
        end;
     end;
     if (Result.dig[0] = 0) then SetLength(Result.dig, 1);
end;


function Sum(lhs,rhs: TLongNumber):TLongNumber;
var i: integer;
    s: QWord;
    TimeResult: QWord;
begin
      s := 0;
      SetLength(Result.dig, high(lhs.dig)+1);
      for i:=0 to high(lhs.dig) do
      begin
           if (i > high(rhs.dig)) then begin
              TimeResult := lhs.dig[i] + 0 + s;
           end
           else begin
                TimeResult := s + lhs.dig[i] + rhs.dig[i];
           end;
           s := TimeResult div Q;
           Result.dig[i] := TimeResult mod Q;
           if (i = high(lhs.dig)) and (s > 0) then begin
              SetLength(Result.dig, high(lhs.dig)+2);
              Result.dig[i+1] := s;
           end;
      end;
end;




function Sub(a, b: TLongNumber): TLongNumber;
var
    lhs, rhs: array of QWord;
    s, i: integer;
begin
	s := 0;
    lhs := copy(a.dig);
    rhs := copy(b.dig);
    SetLength(Result.dig, high(lhs)+1);
    for i:=0 to high(lhs) do begin
    	if (i > high(rhs)) then Result.dig[i] := lhs[i] - 0
        else if (lhs[i] < rhs[i]) then begin
        	Result.dig[i] := Q - (rhs[i] - lhs[i]);
            	if (rhs[i+1] = 0) then lhs[i+1] := Q - 1
                else lhs[i+1] -= 1;
            end
        	else Result.dig[i] := lhs[i] - rhs[i];


    end;
    if (Result.dig[0] = 0) then Result := 0;
end;



operator + (const lhs, rhs: TLongNumber) ans: TLongNumber;
var b: TLongNumber;
begin
     b := rhs;
      if (rhs.dig[0] = 0) then begin
         if (rhs.inv = false)then begin
            b := -rhs;
         end;
      end;

      if (b.inv = lhs.inv) then begin
         if ((lhs > b) and (lhs.inv = true)) or ((lhs < b) and (lhs.inv = false)) then begin
            Result := Sum(lhs, b);
            Result.inv := lhs.inv;
         end
         else begin
              Result := Sum(b, lhs);
              Result.inv := b.inv;
         end;

     end
     else begin
          if (CompareModule(lhs, b)) then begin
             Result := Sub(lhs, b);
             Result.inv := lhs.inv;
          end
          else begin
               Result := Sub(b, lhs);
               Result.inv := b.inv;
          end;
     end;

end;



operator - (const lhs, rhs: TLongNumber) ans: TLongNumber;
var buf: TLongNumber;
begin

     if (lhs.inv = rhs.inv) then begin
        if (CompareModule(lhs, rhs)) then begin
           Result := Sub(lhs, rhs);
           Result.inv := lhs.inv;
        end
        else begin
             buf := -lhs;
             Result := Sub(rhs, buf);
             Result.inv := buf.inv;
        end;
     end
     else begin
          if (CompareModule(lhs, rhs)) then begin
             Result.inv := lhs.inv;
             buf := -lhs;
             Result := Sum(lhs, rhs);

          end
          else begin
               Result.inv := lhs.inv;
               buf := -lhs;
               Result := Sum(rhs, lhs);

          end;
     end;
     if (Result.dig[0] = 0) then begin
        Result.inv := true;
     end;
 end;
operator - (const val: TLongNumber) ans: TLongNumber;
begin
     Result := val;
     if (val.inv = true) then begin
        Result.inv := false;
     end
     else begin
          Result.inv := true;
     end;
end;

operator <= (const lhs, rhs: TLongNumber) ans: boolean;

begin
    if (lhs = rhs) or (lhs < rhs) then begin
        Result := true;
     end
    else Result := false;
end;

operator >= (const lhs, rhs: TLongNumber) ans: boolean;

begin
     if (lhs = rhs) or (lhs > rhs) then begin
        Result := true;
     end
     else Result := false;
end;

operator <> (const lhs, rhs: TLongNumber) ans: boolean;

begin
     Result := not (lhs = rhs);


end;

operator < (const lhs, rhs: TLongNumber) ans: boolean;
begin
 if not (lhs = rhs) and not (lhs > rhs) then begin
    Result := true;
 end
 else begin
      Result := false;
 end;

end;

operator > (const lhs, rhs: TLongNumber) ans: boolean;
var lLen, rLen, i: integer;
begin
     lLen := high(lhs.dig);
     rlen := high(rhs.dig);
     if (lhs.inv = false) and (rhs.inv = true) then begin
        Result := false;
        exit;
     end;
     if (lhs.inv = true) and (lhs.inv = false) then begin
        Result := true;
        exit;
     end;
     if (lhs.inv = true) and (rhs.inv = true) then begin
         if (lLen < rLen) then begin
            Result := false;
         end;
         if (lLen > rLen) then begin
            Result := true;
         end;
         if (lLen = rLen) then begin
            for i:=high(lhs.dig)downto 0 do begin
                if (lhs.dig[i] < rhs.dig[i]) then begin
                   Result := false;
                   exit;
                end;
                if (lhs.dig[i] > rhs.dig[i]) then begin
                   Result := true;
                   exit;
                end;
            end;
            Result := false;
         end;
     end;
     if (lhs.inv = false) and (rhs.inv = false) then begin
        if (lLen < rLen) then begin
            Result := true;
         end;
         if (lLen > rLen) then begin
            Result := false;
         end;
         if (lLen = rLen) then begin
            for i:=high(lhs.dig) to 0 do begin
                if (lhs.dig[i] < rhs.dig[i]) then begin
                   Result := true;
                   exit;
                end;
                if (lhs.dig[i] > rhs.dig[i]) then begin
                   Result := false;
                   exit;
                end;
            end;
            Result := false;
         end;

     end;
end;

operator = (const lhs, rhs: TLongNumber) ans: boolean;
var lLen, rLen, i: integer;
begin
     lLen := high(lhs.dig);
      rlen := high(rhs.dig);
      if (rhs.inv = lhs.inv) then begin
         if (lLen = rLen) then begin
            for i:=high(lhs.dig) downto 0 do begin
                if (lhs.dig[i] <> rhs.dig[i]) then begin
                   Result := false;
                   exit;
                end;
            end;
            Result := true;
            exit;
         end
         else begin
              Result := false;
              exit;
         end;
      end
      else begin
           Result := false;
           exit;
      end;
end;

//...

end.