ac1218.pas

来自「这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码」· PAS 代码 · 共 35 行

program tju1218;
const
  modulo=10000;
var
  k,i,p,e,q,a1,a2,b1,b2,c:longint;
function power_mod(x,y:longint):longint;
  var
    m:longint;
  begin
    if y=0 then
      power_mod:=1
    else begin
      m:=sqr(power_mod(x,y shr 1)) mod modulo;
      if odd(y) then power_mod:=(m*x) mod modulo else power_mod:=m;
    end;
  end;
begin
  repeat
    read(k);a2:=1;b2:=0;c:=1;
    for i:=1 to k do begin
      read(p,e);
      if p>2 then begin
        q:=(p-1) mod modulo;
        a1:=a2;b1:=b2;
        a2:=(a1+b1*q) mod modulo;
        b2:=(b1+a1*q) mod modulo;
      end;
      c:=(c*power_mod(p mod modulo,e)) mod modulo;
    end;
    writeln((a2-1+modulo) mod modulo);
    writeln(b2);
    writeln((c-a2-b2+modulo*2) mod modulo);
  until seekeof;
end.