//implementation of few simple arithmetic procedures under big numbers //not very efficient but working properly //author: Michal Pilipczuk //XIV Secondary High School, Warsaw, Poland unit bignumber; interface type mstring=record zn:longint; war:string; end; type wuh=record aa:mstring; bb:mstring; end; procedure initialize; //initializing whole unit, should be done before using any functions below function wch(fu:longint):char; function wlo(c:char):longint; //functions for exporting longints into chars and vice versa function przez2(a:string;spod:longint):string; //dividing by 2 in any system (based on 'spod') function zmienw2(b:string;spod:longint):string; //changing number into binar system from system with base 'spod' (Note: spod should be even) function mn(x,y:string):boolean; //gives true if x<=y function wyczysc(ab:string):string; //clears zeros at the beginning of the number function bezkon(ab:string):string; //clears zeros at the end function bez(tu:string):string; //clears last digit function od(g,h:string):string; //difference between g and h (Note: they should be in binar system and g should be greater or equal) function nwduj(c,d:string):string; //counting gcd of two numbers (Note: they should be in binar system) function modulo(d,r:string):string; //counting d mod r function dod(a,b:string;pod:longint):string; //adding a and b in system with base 'spod' function zmien(co:string;dow:longint):string; //changing binar number into any other system (based on 'dow') function rand(max:string):string; //random, but not very efficient function mul(w,q:string):string; //multiplication of w and q in binar system function poteg(a,b,r:string):string; //power a^b, everything modulo r (Note: a,b,r should be binar) function jacobi(g,d:string):longint; //counts jacobi symbol: g is up d is down, d should be odd function sprawdz(qur:string):boolean; //says if a string is a proper number function longintuj(a:string;base:longint):longint; //makes a longint from a string in a given positional system(base) function millero(pod,po,pw:string):boolean; //function used in counting miller's test function mill(dosp:string;ile:longint):boolean; //using miller's test finds out if dosp is prime. The number of tests is ile. function divid(a,b:string):string; //computes a/b function megadod(a,b:mstring):mstring; //adds two mstrings function megamul(a,b:mstring):mstring; //multiplies two mstrings function rand_prim(bo:string):string; //gives a random prime number lower or equal to bo function megamodu(ga,gb:mstring):mstring; //a modulo operation for mstrings function odw(wej:wuh;paa:mstring):wuh; //used in odwrot function odwrot(t,p:string):string; //computes t^(-1) mod p function wyp(ll:mstring):string; //gives mstring as it should be written function strassen(p:string;ile:longint):boolean; //using strassen's test finds out if dosp is prime. The number of tests is ile. implementation const MAX=10000; //maximum number of digits of numbers used var zera:array[0..MAX] of string; //array of zeros: zera[i] contains string with i zeros :)))) procedure initialize; var ze:string; ku:longint; begin randomize; ze:=''; zera[0]:=''; for ku:=1 to MAX do begin ze:=ze+'0'; zera[ku]:=ze; end; end; function wch(fu:longint):char; begin wch:=chr(fu+48); end; function wlo(c:char):longint; begin wlo:=ord(c)-48; end; function przez2(a:string;spod:longint):string; var k,i,u:longint; pom:string; begin k:=0; pom:=''; for i:=1 to length(a) do begin u:=wlo(a[i])+k*spod; k:=u mod 2; if not((i=1) and ((u shr 1)=0)) then pom:=pom+wch(u shr 1); end; przez2:=pom; end; function zmienw2(b:string;spod:longint):string; begin if b='' then zmienw2:='' else zmienw2:=zmienw2(przez2(b,spod),spod)+wch(wlo(b[length(b)]) mod 2); end; function mn(x,y:string):boolean; var flag:boolean; j:longint; begin if length(x)length(y) then mn:=false else begin flag:=true; for j:=1 to length(x) do begin flag:=(ord(x[j])(pod-1) then begin l:=l-pod; k:=1; end else k:=0; pom:=wch(l)+pom; end; if k=1 then pom:='1'+pom; dod:=pom; end; end; function zmien(co:string;dow:longint):string; var akt,sum:string; v:longint; begin akt:='1'; sum:=''; for v:=length(co) downto 1 do begin if co[v]='1' then sum:=dod(sum,akt,dow); akt:=dod(akt,akt,dow); end; zmien:=sum; end; function rand(max:string):string; var t:longint; pom:string; begin pom:=''; for t:=1 to length(max) do begin pom:=pom+wch(random(2)); end; pom:=wyczysc(pom); if ((mn(max,pom)) or (pom='') or (max=pom)) then rand:=rand(max) else rand:=pom; end; function mul(w,q:string):string; var pom:string; k:longint; begin if mn(w,q) then mul:=mul(q,w) else begin pom:=''; for k:=length(q) downto 1 do if q[k]='1' then pom:=dod(pom,(w+zera[length(q)-k]),2); mul:=pom; end; end; function poteg(a,b,r:string):string; var akt,pocz:string; k:longint; begin if ((a=r) or (a='')) then poteg:='' else begin if not(mn(a,r)) then poteg:=poteg(modulo(a,r),b,r) else begin akt:=a; pocz:='1'; for k:=length(b) downto 1 do begin if b[k]='1' then begin pocz:=modulo((mul(pocz,akt)),r); end; akt:=modulo((mul(akt,akt)),r); end; poteg:=pocz; end; end; end; function resztymod8(a:string):longint; var u:longint; begin if a='1' then exit(1); if a='11' then exit(-1); if a='101' then exit(-1); if a='111' then exit(1); u:=length(a); resztymod8:=resztymod8(wyczysc(a[u-2]+a[u-1]+a[u])); end; function resztymod4(a:string):longint; var u:longint; begin if a='1' then exit(1); if a='11' then exit(-1); u:=length(a); resztymod4:=resztymod4(wyczysc(a[u-1]+a[u])); end; function faf(oi,pu:string):longint; begin if (resztymod4(oi)+resztymod4(pu))<0 then faf:=(-1) else faf:=1; end; function jacobi(g,d:string):longint; begin if g='' then jacobi:=0 else begin if g='1' then jacobi:=1 else begin if ((d=g) or (mn(d,g))) then jacobi:=jacobi(modulo(g,d),d) else begin if g[length(g)]='0' then jacobi:=resztymod8(d)*jacobi(bez(g),d) else begin jacobi:=(faf(g,d)*jacobi(d,g)); end; end; end; end; end; function sprawdz(qur:string):boolean; var f,h:longint; flag:boolean; begin flag:=true; for f:=1 to length(qur) do begin h:=wlo(qur[f]); if ((h<0) or (h>9)) then begin flag:=false; break; end; end; sprawdz:=flag; end; function longintuj(a:string;base:longint):longint; var f,g,h:longint; begin f:=0; h:=1; for g:=length(a) downto 1 do begin f:=f+wlo(a[g])*h; h:=h*base; end; longintuj:=f; end; function millero(pod,po,pw:string):boolean; var w1,w2:string; flag2:boolean; l:longint; begin w1:='1'; flag2:=true; for l:=1 to length(pw) do begin w2:=modulo(mul(w1,w1),po); if ((w2='1') and (not((w1='1') or (w1=pw)))) then begin flag2:=false; break; end; if pw[l]='1' then w1:=modulo(mul(w2,pod),po) else w1:=w2; end; millero:=((flag2)and(w1='1')); end; function mill(dosp:string;ile:longint):boolean; var ggg,fff:string; t:longint; flag:boolean; begin if dosp[length(dosp)]='0' then mill:=false else begin ggg:=od(dosp,'1'); flag:=true; for t:=1 to ile do begin fff:=rand(ggg); flag:=millero(fff,dosp,ggg); if not(flag) then break; end; mill:=flag; end; end; function divid(a,b:string):string; var wynf,za:string; begin if b='' then divid:='error' else begin wynf:=zera[length(a)]; while (mn(b,a) or (a=b)) do begin za:=b+zera[length(a)-length(b)]; if mn(a,za) then begin za:=b+zera[length(a)-length(b)-1]; wynf[length(wynf)-length(a)+1+length(b)]:='1'; end else begin wynf[length(wynf)-length(a)+length(b)]:='1'; end; a:=od(a,za); end; divid:=wyczysc(wynf); end; end; function megadod(a,b:mstring):mstring; var pomis:mstring; begin if a.zn