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

{$mode objfpc}

interface

const
        TRUE_BASE = qword(1) shl 32;
	MIN_BASE = 2; MAX_BASE = 36;

type
	//Тип длинного целого:
	TLongNumber = record
		dig: array of uint32;	//Буфер, хранящий в себе цифры числа;
		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

//Здесь нужно дописать реализацию объявленных выше функций!

function ToChar(a:uint32): char;
const s:string='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
begin
   ToChar:=s[a+1];
end;

function ToQword(a:char): QWord;
const s:string='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
begin
   ToQword:= pos(a,s)-1;
end;
function MultLongLong(lhs,rhs:TLongNumber; inv:boolean):TLongNumber;
var i,j,remain:uint64;
begin
     SetLength(result.dig,length(lhs.dig) + length(rhs.dig));
     result.inv := inv;
     for i := 0 to length(lhs.dig)-1 do
     begin
          remain := 0;
          for j := 0 to length(rhs.dig)-1 do
          begin
               remain := remain + lhs.dig[i] * rhs.dig[j] + Result.dig[i+j];
               Result.dig[i+j] := remain mod TRUE_BASE;
               remain := remain div TRUE_BASE;
          end;
          if remain > 0 then
          Result.dig[i + length(rhs.dig)] += remain;
     end;
end;

function MutlLongShort(lhs:TLongNumber; rhs:int32; lengthLong:uint32; invLong:boolean):TLongNumber;
var i,remain:qword;
invShort:boolean;
begin
     invShort := true;
     if rhs < 0 then
     begin
          invShort := false;
          rhs := abs(rhs);
     end;
     if invLong = invShort then
        lhs.inv := true
     else
         lhs.inv := false;
     if (lhs.dig[lengthLong - 1] > TRUE_BASE div rhs) then
        SetLength(lhs.dig, lengthLong + 1);
     remain := 0;
     for i := 0 to (lengthLong - 1) do
     begin
          remain := remain + lhs.dig[i] * rhs;
          lhs.dig[i] := remain mod TRUE_BASE;
          remain := remain div TRUE_BASE;
     end;
     if remain > 0 then
        lhs.dig[lengthLong] += remain;
     exit(lhs);
end;
function Swap(lhs,rhs:TLongNumber):TLongNumber;
var t:TLongNumber;
begin
     t:=rhs;
     rhs:=lhs;
     lhs:=t;
end;

function Sum(lhs,rhs:TLongNumber; n1,n2:uint32; inv:boolean):TLongNumber;
var ost:uint32;
    i:uint32;
begin
     ost := 0;
     i := 0;
     if (lhs.dig[n2 - 1] > TRUE_BASE - rhs.dig[n2 - 1]) then
        setLength(lhs.dig,n1 + 1);
     for i := 0 to n2 - 1 do
     begin
          ost := lhs.dig[i] + rhs.dig[i] + ost;
          lhs.dig[i] := ost mod TRUE_BASE;
          ost := ost div TRUE_BASE;
     end;
     for i:= n2 to n1 do
     begin
          if ost = 0 then break;
          ost:=lhs.dig[i] + ost;
          lhs.dig[i] := ost mod TRUE_BASE;
          ost := ost div TRUE_BASE;
     end;
     lhs.inv := inv;
     exit(lhs);
end;

function Min(lhs,rhs:TLongNumber):TLongNumber;
var Inv:boolean;
    i,t:uint32;
begin
     lhs.inv := true;
     rhs.inv := true;
     inv:=lhs.inv;
     i:= 0;
     t:= 0;
     if rhs > lhs then
     begin
          swap(lhs,rhs);
          lhs.inv := not(inv);
     end
     else
          lhs.inv := inv;
     for i := 0 to length(rhs.dig) - 1 do
     begin
          t := lhs.dig[i] - rhs.dig[i] - t;
          if (t < 0) then
          begin
               lhs.dig[i] := TRUE_BASE-abs(t);
               t := 1;
          end
          else
          begin
               lhs.dig[i] := t;
               t := 0;
          end
     end;
     for i := length(rhs.dig) to length(lhs.dig) - 1 do
     begin
          if t = 0 then
             break;
          t := lhs.dig[i] - t;
          if (t < 0) then
          begin
               lhs.dig[i] := TRUE_BASE + t;
               t := 1;
          end
          else
          begin
               lhs.dig[i] := t;
               t := 0;
          end;

     end;
     exit(lhs);
end;

function FromString(const str: AnsiString; base: TBase): TLongNumber;
var
  n: uint32;
  i,k: integer;
  ans: TLongNumber;
begin
     ans:=0;
     k:=1;
     if str[1] = '-' then
         k+=1;
     for i:=k to Length(str) do begin
         n:= ToQword(str[i]);
         ans:=ans*base;
         ans:=ans+n;
         end;
     if str[1] = '-' then
         ans.inv:= False
     else
         ans.inv:= True;
     fromString:= ans;
end;

function toString(const val: TLongNumber; base: TBase): AnsiString;
var
   str:AnsiString;
   r:uint32;
   loc1, loc2: TLongNumber;
begin
   loc1.inv:=val.inv;
   loc2:=val;
   loc2.inv:= True;
   if (Length(val.dig) = 1) and (val.dig[0] = 0) then
       str:='0'
   else begin
       while loc2 <> 0 do begin
           loc2:= divmod(loc2, base, r);
           str:= ToChar(r) + str;
           end;
       if loc1.inv = False then
           str:= '-' + str;
       end;
   toString:= str;
end;

operator := (val: int64) res: TLongNumber;
var
   i: integer;
   q: QWord;
begin
   q:= QWord(1) shl 32;
   SetLength(res.dig, 0);
   i:=0;
   if val >= 0 then
       res.inv:= True
   else
       res.inv:= False;
   val:= abs(val);
   while (val > 0) do begin
       SetLength(res.dig, i+1);
       res.dig[i]:= val mod q;
       val:= val div q;
       inc(i);
       end;
   if Length(res.dig) = 0 then begin
      SetLength(res.dig,1);
      res.dig[0] := 0;
      end;
end;


function divmod(const lhs: TLongNumber; rhs: int32;
out rem: uint32): TLongNumber;
var i:uint32;
remain:qword;
invShort:boolean;
begin
SetLength(Result.dig,length(lhs.dig));
invShort := true;
if rhs < 0 then
begin
invShort := false;
rhs := abs(rhs);
end;
if lhs.inv = invShort then
Result.inv := true
else
Result.inv := false;
remain := 0;
for i := length(lhs.dig) - 1 downto 0 do
begin
remain := lhs.dig[i] + remain * TRUE_BASE;
result.dig[i] := remain div rhs;
remain := remain mod rhs;
end;
rem := remain;
end;



operator / (const lhs: TLongNumber; rhs: int32) ans: TLongNumber;
var ost:uint32;
begin
     ans := divmod(lhs,rhs,ost);
end;

operator * (const lhs: TLongNumber; rhs: int32) ans: TLongNumber;
begin
     ans := MutlLongShort(lhs,rhs,length(lhs.dig),lhs.inv);
end;

operator * (lhs: int32; const rhs: TLongNumber) ans: TLongNumber;
begin
     ans := MutlLongShort(rhs,lhs,length(rhs.dig),rhs.inv);
end;

operator * (const lhs, rhs: TLongNumber) ans: TLongNumber;
begin
     if lhs.inv = rhs.inv then
        ans := MultLongLong(lhs,rhs,true)
     else
        ans := MultLongLong(lhs,rhs,false);
end;

operator + (const lhs, rhs: TLongNumber) ans: TLongNumber;
begin
     if (lhs.inv = rhs.inv) then
     begin
          if length(lhs.dig) >= length(rhs.dig) then
             ans := sum(lhs,rhs,length(lhs.dig),length(rhs.dig),lhs.inv)
          else
             ans := sum(rhs,lhs,length(rhs.dig),length(lhs.dig),lhs.inv);
     end
     else
     begin
          ans := min(lhs,rhs);
     end;
end;

operator - (const lhs, rhs: TLongNumber) ans: TLongNumber;
begin
     if lhs.inv = rhs.inv then
        ans := min(lhs,rhs)
     else
     begin
          if length(lhs.dig) >= length(rhs.dig) then
             ans:=sum(lhs,rhs,length(lhs.dig),length(rhs.dig),lhs.inv)
          else
             ans:=sum(rhs,lhs,length(rhs.dig),length(lhs.dig),lhs.inv);
     end;

end;

operator - (const val: TLongNumber) ans: TLongNumber;
begin
     ans := val;
     ans.inv := not(val.inv);
end;

operator <= (const lhs, rhs: TLongNumber) ans: boolean;
begin
     ans := (rhs > lhs) or (lhs = rhs);
end;

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

operator <> (const lhs, rhs: TLongNumber) ans: boolean;
begin
     ans := not(lhs = rhs);
end;

operator < (const lhs, rhs: TLongNumber) ans: boolean;
begin
     ans := (rhs > lhs) and (rhs<>lhs);
end;

operator > (const lhs, rhs: TLongNumber) ans: boolean;
var i,lengthLeft,lengthRight:uint32;
begin
    ans := true;
    lengthLeft := length(lhs.dig);
    lengthRight := length(rhs.dig);
    if lhs.inv = rhs.inv then
    begin
      if lhs.inv = true then
      begin
        if(lengthLeft < lengthRight) then exit(false)
        else if (lengthLeft = lengthRight) then
        begin
          for i := lengthLeft - 1 downto 0 do
          begin
            if (lhs.dig[i] = rhs.dig[i]) then
              ans := false
            else if (lhs.dig[i] > rhs.dig[i]) then
              exit(true)
            else
              exit(false);
          end;
        end;
      end
      else
      begin
      if lengthLeft > lengthRight then exit(false)
         else if (lengthLeft = lengthRight) then
         begin
           for i := lengthLeft - 1 downto 0 do
           begin
              if (lhs.dig[i] = rhs.dig[i]) then
                ans:=false
              else if (lhs.dig[i] < rhs.dig[i]) then
                 exit(true)
              else
                 exit(false);
           end;
         end;
      end;
    end
    else
    if rhs.inv = true then
      ans := false;
end;

operator = (const lhs, rhs: TLongNumber) ans: boolean;
begin
     ans := (not((lhs > rhs) or (rhs > lhs)));
end;

end.