label
        chknext;
var
        l,i,j:longint;
        k:array[1..30]of longint;
        p:array[1..9600]of longint;
        nsize,size:longint;

function calcmod(moder:longint):longint;
var i,x:longint;
begin
        x:=0;
        for i:=nsize downto 1 do
        begin
                x:=x*10000+k[i];
                x:=x mod moder;
        end;
        calcmod:=x;
end;


function iszero:boolean;
begin
        iszero:=(nsize=1)and(k[nsize]=0);
end;

procedure getnum;
var s,ts:string;
    c:char;
begin
        s:='';nsize:=0;
        repeat
                read(c);
                if not (('0'<=c)and(c<='9')) then break;
                s:=s+c;
        until false;
        while length(s)>0 do
        begin
                ts:=copy(s,length(s)-3,4);
                inc(nsize);
                val(ts,k[nsize]);
                s:=copy(s,1,length(s)-4);
        end;
end;

function mod_exp(a,b,c:longint):longint;
var d,ans:int64;
begin
        ans:=1;d:=a mod c;
        while b>0 do
        begin
                if b mod 2=1 then ans:=ans*d mod c;
                d:=d*d mod c;
                b:=b shr 1;
        end;
        mod_exp:=ans;
end;

function miller_rabbin(x:longint):boolean;
begin
        if (x<>2)and(mod_exp(2,x-1,x)<>1) then exit(false);
        if (x<>3)and(mod_exp(3,x-1,x)<>1) then exit(false);
        if (x<>5)and(mod_exp(5,x-1,x)<>1) then exit(false);
        if (x<>7)and(mod_exp(7,x-1,x)<>1) then exit(false);
        if (x<>11)and(mod_exp(11,x-1,x)<>1) then exit(false);
        if (x<>13)and(mod_exp(13,x-1,x)<>1) then exit(false);
        miller_rabbin:=true;
end;


begin
        size:=1;
        p[1]:=2;
        i:=3;
        while i<100000 do
        begin
                if miller_rabbin(i) then
                begin
                        inc(size);
                        p[size]:=i;
                end;
                inc(i,2);
        end;
        inc(size);p[size]:=maxlongint;
        repeat
                chknext:
                getnum;
                readln(l);
                if iszero and (l=0) then break;

                i:=1;
                while p[i]<l do
                begin
                        if calcmod(p[i])=0 then
                        begin
                                writeln('BAD ',p[i]);
                                goto chknext;
                        end;
                        inc(i);
                end;
                writeln('GOOD');
        until false;
end.

• 好久不见人用GOTO了。。。 (2783) e_at_fdu 2005-10-07 15:52:22
  • Re:好久不见人用GOTO了。。。 (7) wangshuai 2005-10-07 15:56:30
• 即使不wa都tle了 (2783) frkstyc 2005-10-07 16:02:03
  • Re:即使不wa都tle了 (14) wangshuai 2005-10-07 16:05:20
    • 0ms也一样，说白了就是还没tle就已经错了 (18) frkstyc 2005-10-07 16:10:43