4 条评论
-
master_miu LV 0 @ 2013-02-22 11:55:33
this
-
@ 2013-02-22 13:42:59
that
-
-
@ 2013-02-21 22:16:52
目测是你常数写得太大了，快速幂应该使用非递归，素数测试最好使用改进之后的米勒-罗宾测试，正确率更高，而且使用该方法判断2,3,5,7,11,就可以解决int范围内的所有数了。而使用前9个素数可以i解决long long范围
详见matrix67的文章-
@ 2013-02-22 15:39:38
- 用的MR貌似就是那个啥米勒-罗宾测试了吧。。。
-
@ 2013-02-22 16:16:41
- orz。。。
- 改进以后的MR算法咋写，就是用令人费解的*2,3,5,7,11,13,17,19,23,29,31*……来判定？？
-
-
@ 2013-02-21 16:00:10
var
a:array[1..1000000]of longint;
min,max,min1,min2,max1,max2,n,m,i,tot,ch:longint;function power(a,p,t:longint):int64;
begin
if p=0 then exit(1);
a:=a mod t;
power:=power(a,p shr 1,t);
power:=power*power mod t;
if p and 1=1 then power:=(power*a) mod t;
exit;
end;function mr(t:longint):boolean;
var
i,m:longint;
begin
for i:=1 to 32 do
begin
m:=random(t-2)+1;
if power(m,t-1,t)<>1 then exit(false);
end;
exit(true);
end;begin
while not eof do
begin
readln(n,m); tot:=0;
for i:=n to m do
if mr(i) then begin inc(tot); a[tot]:=i; end;
if tot<2 then writeln('There are no adjacent primes.')
else
begin
min:=a[2]-a[1]; max:=a[2]-a[1];
min1:=a[1]; min2:=a[2];
max1:=a[1]; max2:=a[2];
for i:=3 to tot do
begin
ch:=a[i]-a[i-1];
if ch>max then
begin
max:=ch;
max1:=a[i-1];
max2:=a[i];
end;
if ch<min then
begin
min:=ch;
min1:=a[i-1];
min2:=a[i];
end;
end;
writeln(min1,',',min2,' are closest, ',max1,',',max2,' are most distant.')
end;
end;
end. -
@ 2013-02-21 15:59:31
- 求落单的__节操&&RP__，我要捡一点。。。 var a:array[1..1000000]of longint; min,max,min1,min2,max1,max2,n,m,i,tot,ch:longint;
function power(a,p,t:longint):int64;
begin
if p=0 then exit(1);
a:=a mod t;
power:=power(a,p shr 1,t);
power:=power*power mod t;
if p and 1=1 then power:=(power*a) mod t;
exit;
end;function mr(t:longint):boolean;
var
i,m:longint;
begin
for i:=1 to 32 do
begin
m:=random(t-2)+1;
if power(m,t-1,t)<>1 then exit(false);
end;
exit(true);
end;begin
while not eof do
begin
readln(n,m); tot:=0;
for i:=n to m do
if mr(i) then begin inc(tot); a[tot]:=i; end;
if tot<2 then writeln('There are no adjacent primes.')
else
begin
min:=a[2]-a[1]; max:=a[2]-a[1];
min1:=a[1]; min2:=a[2];
max1:=a[1]; max2:=a[2];
for i:=3 to tot do
begin
ch:=a[i]-a[i-1];
if ch>max then
begin
max:=ch;
max1:=a[i-1];
max2:=a[i];
end;
if ch<min then
begin
min:=ch;
min1:=a[i-1];
min2:=a[i];
end;
end;
writeln(min1,',',min2,' are closest, ',max1,',',max2,' are most distant.')
end;
end;
end.
* TLE的大大的。。。
- 1
