MMOD29 - CALCULATE POW(2004,X) MOD 29

Tác giả: flashmt

Ngôn ngữ: Pascal

const ar:array[2..4] of integer=(2,3,167);
var n,re,t,i,j,s:longint;
    m:array[2..4] of longint;
    a:array[2..4,1..100] of longint;
procedure init;
var i,j:byte;
begin
     a[2,1]:=2; a[3,1]:=3; a[4,1]:=22;
     for i:=2 to 4 do
     begin
          m[i]:=2;
          a[i,2]:=(a[i,1]*ar[i]) mod 29;
     end;
     for i:=2 to 4 do
     begin
          while a[i,m[i]]<>a[i,1] do
          begin
               inc(m[i]);
               a[i,m[i]]:=(a[i,m[i]-1]*ar[i]) mod 29;
          end;
          dec(m[i]);
     end;
end;

begin
     init;
     repeat
           read(n);
           if n=0 then break;
           t:=(2*n+1) mod m[2];
           if t=0 then t:=m[2];
           re:=(a[2,t]+28) mod 29;
           for i:=3 to 4 do
           begin
                t:=(n+1) mod m[i];
                if t=0 then t:=m[i];
                dec(t);
                s:=1;
                for j:=1 to t do s:=(s+a[i,j]) mod 29;
                re:=(re*s) mod 29;
           end;
           writeln(re);
     until false;
end.

Download