//implementation of miller test without big numbers (maximum range is range of longint) //author: Michal Pilipczuk //XIV Secondary High School, Warsaw, Poland program miller; uses bignumber; var hand_in:text; i,dl,b,k,t,p:longint; w1,w2:qword; wej:string; flag,flag2:boolean; reprezent:array[0..100] of longint; procedure wyp(a:longint); begin dl:=1; b:=a; while (1=1) do begin reprezent[dl]:=(b mod 2); b:=(b shr 1); if b=0 then break; dl:=dl+1; end; end; function millero(podst:longint):boolean; begin w1:=1; flag2:=true; for k:=dl downto 1 do begin w2:=((w1*w1) mod i); if ((not((w1=1) or (w1=i-1)))and(w2=1)) then begin flag2:=false; break; end; if reprezent[k]=1 then w1:=((w2*podst) mod i) else w1:=w2; end; millero:=((flag2) and (w1=1)); end; begin randomize; assign(hand_in,'/home/k03_a/michaj/.homepage/miller.in'); reset(hand_in); readln(hand_in,wej); close(hand_in); if not(sprawdz(wej)) then writeln('WRONG INPUT') else begin i:=longintuj(wej,10); wyp(i-1); for t:=1 to 20 do begin p:=random(i-1)+1; flag:=millero(p); if not(flag) then break; end; writeln(flag); end; end.