cfjhzcb
(cfjhzcb)
學校
:
Harvard University
編號 : 9545
來源 : [122.96.58.35]
最後登入時間 ：
2010-11-12 19:09:19
var
n,i,t:longint;
p:boolean;
function f(a,b,c:longint):longint;
var
temp:int64;
begin
if b=0 then exit(1);
if b=1 then exit(a mod c);
temp:=sqr(f(a,b div 2,c)) mod c;
if b mod 2=1 then temp:=(temp*a) mod c;
exit(temp);
end;
begin
while not eof do
begin
readln(n);
if n<2 then writeln(1) else if (n=2) or (n=3) or (n=5) or (n=7) then writeln(0) else begin
if (f(2,n-1,n)=1) and (f(3,n-1,n)=1) and (f(5,n-1,n)=1) and (f(7,n-1,n)=1) then writeln(0) else writeln(1); end;
end;
end.
MILLER-RABIN算法 为什么会在1003行WA？
cfjhzcb
(cfjhzcb)
學校
:
Harvard University
編號 : 9545
來源 : [122.96.58.35]
最後登入時間 ：
2010-11-12 19:09:19
var
n,i,t:longint;
p:boolean;
function f(a,b,c:longint):longint;
var
temp:int64;
begin
if b=0 then exit(1);
if b=1 then exit(a mod c);
temp:=sqr(f(a,b div 2,c)) mod c;
if b mod 2=1 then temp:=(temp*a) mod c;
exit(temp);
end;
begin
while not eof do
begin
readln(n);
if n<2 then writeln(1) else if (n=2) or (n=3) or (n=5) or (n=7) then writeln(0) else begin
if (f(2,n-1,n)=1) and (f(3,n-1,n)=1) and (f(5,n-1,n)=1) and (f(7,n-1,n)=1) then writeln(0) else writeln(1); end;
end;
end.
MILLER-RABIN算法 为什么会在1003行WA？
我知道了
sqr有点问题
记下来平方就对了。。。
可惜啊 没破记录 才500多MS 555
cfjhzcb
(cfjhzcb)
學校
:
Harvard University
編號 : 9545
來源 : [122.96.58.35]
最後登入時間 ：
2010-11-12 19:09:19
var
n,i,t:longint;
p:boolean;
function f(a,b,c:longint):longint;
var
temp:int64;
begin
if b=0 then exit(1);
if b=1 then exit(a mod c);
temp:=sqr(f(a,b div 2,c)) mod c;
if b mod 2=1 then temp:=(temp*a) mod c;
exit(temp);
end;
begin
while not eof do
begin
readln(n);
if n<2 then writeln(1) else if (n=2) or (n=3) or (n=5) or (n=7) then writeln(0) else begin
if (f(2,n-1,n)=1) and (f(3,n-1,n)=1) and (f(5,n-1,n)=1) and (f(7,n-1,n)=1) then writeln(0) else writeln(1); end;
end;
end.
MILLER-RABIN算法 为什么会在1003行WA？
我知道了
sqr有点问题
记下来平方就对了。。。
可惜啊 没破记录 才500多MS 555
哈哈破纪录啦 400ms 哈哈哈
| 544954 | cfjhzcb |  AC (400ms, 620KB) | PASCAL | 582 Bytes | 2010-08-16 11:08 |
| 544951 | cfjhzcb | AC (460ms, 616KB) | PASCAL | 601 Bytes | 2010-08-16 11:05 |
| 544489 | liouzhou_101 | AC (464ms, 616KB) | PASCAL | 799 Bytes | 2010-08-15 13:35 |
| 544947 | cfjhzcb | AC (512ms, 620KB) | PASCAL | 624 Bytes | 2010-08-16 11:01 |
| 544487 | liouzhou_101 | AC (688ms, 616KB) | PASCAL | 800 Bytes | 2010-08-15 13:33 |
| 544482 | liouzhou_101 | AC (920ms, 620KB) | PASCAL | 800 Bytes | 2010-08-15 13:26 |
| 544464 | liouzhou_101 | AC (940ms, 616KB) | PASCAL | 804 Bytes | 2010-08-15 13:00 |
| 544480 | liouzhou_101 | AC (1.1s, 608KB) | PASCAL | 788 Bytes | 2010-08-15 13:24 |
| 474745 | guest | AC (1.1s, 688KB) | PASCAL | 1,043 Bytes | 2010-05-03 10:47 |