mod.pas

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

program mod1(input,output);
var b,p,k,i,len,rest,temp:longint;
    binary:array[1..32] of longint;
begin
  assign(input,'mod.in');
  assign(output,'mod.out');
  reset(input);
  rewrite(output);
  readln(b,p,k);   {输入三个数}
  len:=0;
  temp:=p;
  while temp<>0 do    {存放p的二进制转换}
    begin
      len:=len+1;
      binary[len]:=temp mod 2;
      temp:=temp div 2
    end;
  rest:=1;
  for i:=len downto 1 do    {用二分法实现b^p mod k}
    begin
      temp:=rest*rest mod k;
      if binary[i]=1 then rest:=b mod k * temp mod k    {如果是奇数，就多乘b}
                     else rest:=temp     {否则就是rest*rest}
    end;
  writeln(b,'^',p,' mod ',k,' = ',rest);   {输出b^p mod k}
  close(input);
  close(output)
end.