> 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.

• Re:即使不wa都tle了 (14) wangshuai 2005-10-07 16:05:20
  • 0ms也一样，说白了就是还没tle就已经错了 (18) frkstyc 2005-10-07 16:10:43