悬赏了(200) [复制链接]

能否不用exp ln?
只是费马小定理!

var
n,r,t:int64;

procedure m(a:longint);
var
  i:longint;
begin
  for i:=1 to a do
  r:=r*n mod 1000003;
end;

procedure l(a:longint);
var
  i:longint;
begin
  for i:=1 to a do
  t:=t*n mod 1000002;
end;

begin
read(n);
if n=2
  then write(16)
  else
  if n<=7
    then
    begin
      r:=1;
      t:=round(exp(n*ln(n)));
      m(t);
      write(r);
    end
    else
    begin
      t:=1;
      l(n);
      r:=1;
      m(t);
      write(r);
    end;
end.

我第一
数据测试到
10000000用时2秒以内
20000000用时不超过3秒

重做了一遍
增加了1000003的倍数的处理
减少了小于7时的判断（本来以为小于7时不能用费马小定理）
var
n,r,t:int64;
procedure power(a,b:int64;var t:int64);
var
  i:longint;
begin
  for i:=1 to a do
  t:=t*n mod b;
end;

begin
read(n);
if n mod 1000003=0
  then write(0)
  else
  if n=2
    then write(16)
    else
    begin
      r:=1;
      power(n,1000002,r);
      t:=1;
      power(r,1000003,t);
      write(t);
    end;
end.

不能用exp ln来算
因为算到n=5时 数据有2084位就算是int64也存不下

恭喜xyj,获赏金200!

此题到此为止,谢谢参与,会有新题哦

xyj 收到赏金请回复！

赏金已收到